XX理工大学数据结构期末试卷.doc

一、选择题〔每题2分共20分〕
1．假设长度为n的线性表(a1, a2,…, an)采用顺序存储，删除它的第i个数据元素，需要依次向前移动 个数据元素。
A. n-ii-1

2． 在一个单链表head中，假设要在指针p所指结点后插入一个q指针所指结点，那么执行_____。
A. p->next=q->next; q->next=p;
B. q->next=p->next; p=q;
C. p->next=q->next; p->next=q;
D. q->next=p->next; p->next=q;

3．栈是一种 的线性表。
A. 只允许在一端进展插入和在另一端进展删除
B. 只允许在一端进展插入和删除
C. 只允许在两端进展插入和删除
D. 允许在中间部位进展插入和删除

4．算术表达式a×b+c/d的逆波兰式是______。
A. ab×cd+/ B. ab×c/d+ C. ab×cd/+ D. ab+×cd/

5．循环队列用数组A[0，m-1]存放其元素值，其头尾指针分别是front和rear，那么当前队列中的元素个数是〔〕。
A．(rear-front+m)%m B．read-front+1
C．read-front-1 D．read-front

6．设二维数组a[0…m-1][0…n-1]按行优先顺序存储在首地址为loc(a00)的存储区域中，每个元素占d个单元，那么aij的地址为________。
A. loc(a00) +( i×n+ j) ×d B. loc(a00) +(j×m+i) ×d
C. loc(a00) +((j-1)×n+i-1) ×d D. loc(a00) +((j-1)×m+i-1) ×d

7．对于二叉树来说,第i层上至多有____个结点。
A．2i B． 2i-1 C．2i-1 D．2i-1-1

8．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当二分查找值为82的结点时，〔 〕次比拟后查找成功。
A．1 B．2 C．4 D．8

9．设哈希表长m=11，哈希函数H〔key〕=key%11。表中已有4个结点：addr〔15〕=4， addr〔38〕=5，addr〔61〕=6，addr〔84〕=7，其余地址为空，如果线性探测再散列处理冲突，关键字为49的结点地址是 。
A．3 B．5 C．8 D．9

10．用某种排序方法对线性表〔25,84,21,47,15,27,68,35,20〕进展排序时，元素序列的变化情况如下：
25,84,21,47,15,27,68,35,20
15,84,21,47,25,27,68,35,20
15,20,21,47,25,27,68,35,84
15,20,21,25,47,27,68,35,84
．
．
15,20,21,25,27,35,47,68,84
那么采用的排序方法是〔 〕。
A．冒泡排序 B．快速排序 C．归并排序 D．选择排序

二、求解题
1．二叉树的扩展前序序列：FKHφφBEφφφGAφφDφCφφ.请画出该二叉树并写出该树的中序和后序序列。〔12分〕

2．画出以下树对应的二叉树。〔10分〕

G=<V,E>,其中V={a,b,c,d,e},E={(a,b),(a,e),(b,e),(b,c),(c,e),(e,d)}.请画出图G的邻接矩阵,邻接表。从结点a出发,分别写出按深度优先搜索法和广度优先搜索法进展遍历的结点序列。(12分)

4．从空的二叉排序树开场依次插入30，18,11,17,7,5,13,41,29,37,23,19。画出该二叉排序树。〔9分〕

5．分别写出对序列 10,18,11,17,7,5,13,41,29,37,23,19,25进展快速排序和冒泡排序的过程。(16分)

三、写出以下算法的功能或输出结果

1.typedef struct List
{ int number;
struct List *next;
} Node，*Link;
void func1(Link p)//p指向单链表
{
while(p!=NULL)
{ printf(“%d\n〞,p->number);
p=p->next;
}
}
功能是 。

2.写出以下程序段的运行结果〔栈中的元素类型是char〕：
main(　)
{ SEQSTACK s,*p;
char x, y;
p = &s;
initstack(p);
x = ‘c’; y = ‘k’;
push(p,x); push(p,’a′); push(p,y);
x = pop(p);
push(p,’t′);
push(p,’s′);
while(!empty(p))
{ y = pop(p);
printf(″%c″,y);}
printf(″%c＼n″,x);
}
运行结果是 。

3．int func3 (int r[ ], int n, int k)
{ int i,low=0, high=n-1, mid, find=0;
while (low<=high &&find==0)
{ mid=(low+high)/2;
if (k<r[mid]) high=mid-1;
else if (k>r[mid]) low=mid+1;
else ｛i＝mid;
find=1;｝
}
if (!find) return -1;
return i;
}
功能是 。

四、读程填空
1．以下算法创立n个元素的带头单链表.
typedef struct lnode
{ int data;
struct lnode *next;
}lnode,*linklist ;

void create(linklist &head, int n)
{linklist p; int i;
head=(linklist)malloc(sizeof(lnode));
A ;
for(i=n;i>0;i--)
{p =(linklist)malloc(sizeof(lnode));
scanf(“%d〞,&p->data);
B ;
C ;
}
}

2．完成以下插入排序算法。
typedef struct node
{int key;
int data;
}NODE;
void insert(NODE r[ ],int n) // r[0]为哨兵
{int i,j;
for(i=2;i<=n;i++)
if ( A )
{r[0]=r[i];j=i-1;
while ( B )
r[j+1]=r[j--];
C ;
}
}

参考答案

一、A D B C A A B C C D
二、
1. F 1分

K G 2分

H B A D 2分

E C 1分

中序序列:HKEBFAGDC 3分
后序序列: HEBKACDGF 3分

2.
B不
A
E
C
F
J
D
I
G
H
K

3.
邻接矩阵：

邻接表：

b不
a
e
c
d

Dfs: a b c e d
其他:a e d c b

bfs: a b e c d
其他:a e b d c , a e b c d

4,

18不
30
23
11
7
5
17
13
29
19
41
37

5.
快速排序：
10,18,11,17,7,5,13,41,29,37,23,19,25
5,7,10,17,11,18,13,41,29,37,23,19,25
5,7,10,13,11,17,18,41,29,37,23,19,25
5,7,10, 11, 13,17, 18,41,29,37,23,19,25
5,7,10, 11, 13,17, 18,25,29,37,23,19,41
5,7,10, 11, 13,17, 18,19,23,25,37,29,41
5,7,10, 11, 13,17, 18,19,23,25, 29,37,41

冒泡排序：
10,18,11,17,7,5,13,41,29,37,23,19,25
i=1: 10,11,17,7,5,13,18,29,37,23,19,25,41
i=2: 10,11,7,5,13,17,18,29,23,19,25,37
i=3: 10,7,5,11,13,17,18,23,19,25,29
i=4: 7,5,10,11,13,17,18,19,23,25
i=5: 5,7,10,11,13,17,18,19,23

三、

2. stack

四、 1. A: head->next=NULL B:p->next=head->next C: head->next=p

2. A: r[i].key<r[i-1].key B:r[0].key<r[j].key C:r[j+1]=r[0]

【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】

页脚下载后可删除，如有侵权请告知删除！