南邮通达2015数据结构B刷题试题及答案

３．

在链式存储结构上设计直接插入排序算法

在链式存储结构上设计直接插入排序算法

void straightinsertsort(lklist *&head) {

lklist *s,*p,*q; int t;

if (head==0 || head->next==0) return;

else for(q=head,p=head->next;p!=0;p=q->next) {

for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p;

else{q->next=p->next; p->next=s->next; s->next=p;

t=p->data;p->data=s->data;s->data=t;}

} }

25

数据结构试卷（七）

一、选择题(30分)

1．设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。 (A) 2n

(B) n

(C) n/2

(D) n(n-1)

2．设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。 (A) n

(B) n-1

(C) 2n

(D) 2n-1

3．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。

(A) 40，42，60，55，80，85 (C) 42，40，55，60，80，85

(B) 42，45，55，60，85，80 (D) 42，40，60，85，55，80

4．（ ）二叉排序树可以得到一个从小到大的有序序列。

(A) 先序遍历

(B) 中序遍历 (C) 后序遍历 (D) 层次遍历

5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。

(A) 2i+1

(B) 2i

(C) i/2

(D) 2i-1

6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。

(A) O(n)

(B) O(nlog2n)

(C) O(n2)

(D) O(n3/2)

7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。

(A) head==0

(C) head->next==head

(B) head->next==0 (D) head!=0

8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。 (A) 20

(B) 256

(C) 512

(D) 1024

9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。 (A) 1

(B) 2

(C) 3

(D) 4

10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。

26

(A) top=top+1; (C) top->next=top; (B) top=top-1;

(D) top=top->next;

四、算法设计题(20分)

1. 设计在链式结构上实现简单选择排序算法。 设计在链式结构上实现简单选择排序算法。

void simpleselectsorlklist(lklist *&head) {

lklist *p,*q,*s; int min,t;

if(head==0 ||head->next==0) return; for(q=head; q!=0;q=q->next) {

min=q->data; s=q;

for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s!=q){t=s->data; s->data=q->data; q->data=t;} } }

2. 设计在顺序存储结构上实现求子串算法。 设计在顺序存储结构上实现求子串算法。

void substring(char s[ ], long start, long count, char t[ ]) {

long i,j,length=strlen(s);

if (start<1 || start>length) printf(\ else if (start+count-1>length) printf(\else { for(i=start-1,j=0; i

3. 设计求结点在二叉排序树中层次的算法。 设计求结点在二叉排序树中层次的算法。

int lev=0;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void level(bitree *bt,int x) {

if (bt!=0)

{lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);} }

27

28