数据结构(第二版)-模拟试题自测卷AB卷带答案2.doc

试卷三
一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分)
1．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（ ）
A.S上的算法 B.S的存储结构
C.在S上的一个基本运算集 D.在S上的所有数据元素
2．下列说法正确的是（ ）
A.线性表的逻辑顺序与存储顺序总是一致的
B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续
C.线性表的线性存储结构优于链式存储结构
D.每种数据结构都具有插入、删除和查找三种基本运算
3．稀疏矩阵一般采用（ ）方法压缩存储。
A.三维数组 B.单链表
C.三元组表 D.散列表
4.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。
A. s↑.next:=p；p↑.next=s;
B. s↑.next:=p↑.next;p↑.next:=s；
C. s↑.next:=p↑.next;p:=s;
D. p↑.next:=s;s↑.next=p;
5.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是( )。
A.110 B.108 C.100 D.120
6.下面的二叉树中，( )不是完全二叉树。
7.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始堆为( )。
A.78、47、61、33、39、80 B.80、78、61、33、39、47
C.80、78、61、47、39、33 D.80、61、78、39、47、33
8.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( )
A.q->right=s; s->left=q; q->right->left=s; s->right=q->right;
B.s->left=q; q->right=s; q->right->left=s; s->right=q->right;
C.s->left=q; s->right=q->right; q->right->left=s; q->right=s;
D.以上都不对
9.由下列三棵树组成转的森林换成一棵二叉树为( )

10. for（i=0；i<m；i++）
for（j=0；j<t；j++）
c［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的时间复杂度为（ ）
A.O（m+n×t） B.O（m+n+t）
C.O（m×n×t） D.O（m×t+n）
11.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（ ）
A.Q［4］ B.Q［5］
C.Q［14］ D.Q［15］
12.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ ）
A.LOC+28L B.LOC+36L
C.LOC+50L D.LOC+52L
13.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ ）
A.插入和快速 B.冒泡和快速
C.选择和插入 D.选择和冒泡
14.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段
p=h;
while (p->next->next!=h)
p=p->next;
p->next=h;
后（其中，p->next为p指向结点的指针域），则( )
A. p->next指针指向链尾结点 B. h指向链尾结点
C. 删除链尾前面的结点 D. 删除链尾结点
15.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )
A.高度等于其结点数 B.任一结点无左孩子
C.任一结点无右孩子 D.空或只有一个结点
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。
17．给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过 次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。
18．树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的 关系。
19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____________。
20.数据表示和________________是程序设计者所要考虑的两项基本任务。
21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为 _________。
22.深度为k的二叉树至多有 _________个结点，最少有 _________个结点。
23．在堆排序和快速排序中，若原始记录已基本有序，则较适合选用 。
24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。
25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。
26.三个结点可构成________种不同形态的二叉树。
27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素ai和ai+1的值，若ai的值大于ai+1的值，则交换ai和ai+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_________。
28.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中________个用于链接孩子结点。
三、应用题（本大题共5小题，每小题6分，共30分）
29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。
30．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。
31.已知某二叉树的顺序存储结构如图所示，试画出该二叉树，并画出其二叉链表表示。
A
B
C
D

E

F
G
32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列
作升序排序，并给出每一趟的排序结果。
33.请按照数列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序树。
四、算法设计题(本大题共3小题，共14分)
34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。（4分）
35.某带头结点的单链表的结点结构说明如下： （6分）
typedef struct node1
{
int data;
struct node1 *next
}node；
试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。
36.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。（4分）

参考答案
一、选择题（本题共30分,每题2分）
1、 C 2、B 3、C 4、B 5、B 6、C 7、B 8、C 9、A 10、C 11、B 12、D 13、C 14、D 15、A
二、填空题（本题共26分,每小题2分）
16、树状结构 17、 n-1
18、逻辑 19、 n/2
20、数据处理 21、 front==(rear+1)%n
22、2k-1，k 23、堆排序
24、中序 25、有序
26、5 27、冒泡排序
28、n-1
三、应用题（本题共30分，每小题6分）
29、
A
B
C
D
G
后序序列：CDBGFEA (3分)
F
E

(3分)
30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);
pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2);
A
C
D
E
F
G
32、
第1趟： [37] 38 [73 52 40 64 56 43]
第2趟： 37 38 [43 52 40 64 56] 73
第3趟： 37 38 [40] 43 [52 64 56] 73
第4趟： 37 38 40 43 52 [64 56] 73
第5趟： 37 38 40 43 52 [56] 64 73
第6趟： 37 38 40 43 52 56 64 73
31、
B
A
C
D
E
F
G
A
B ∧ NULL
∧ C ∧
ROOT
∧ D
E
∧ F ∧
∧ G ∧

33、
28
12
45
20
18
33
55
37

四、算法设计题（本题共14分）
34、(4分)
typedef struct node *pointer;
struct node
{
datatype data;
pointer next;
};
typedef pointer lklist;
void insert_lklist(lklist head,datatype x,int i)
{
pointer *p,*s;
p=head;
j=0;
while((p->next!=NULL)&&(j<i-1))
{p=p->next;j++;}
if(j!=i-1)
{printf("不存在第i个位置");
break();
}
else {s=malloc(size);s->data=x;
s->next=p->next;
p->next=s;}
}
35、(6分)
int copy(node *head1,node *head2)
{
Node *p,*s;
P=head1->next;
If(p!=NULL)
{
*r=malloc(size);
r->data=p->data;
head2=r;
p=p->next;
}
else
{head2=NULL;
Return(0);
}
While(p!=NULL)
{ *s=malloc(size);
s->data=p->data;
r->next=s;
r=s;
p=p->next;
}
r->next=NULL;
return(1);
}
36、（4分）
typedef char DataType;
typedef struct node
{
DataType data;
struct node *lchild, *rchild;
} BinTNode;
typedef BinTNode *BinTree;
int nodes(BinTree T)
{
int num1,num2;
if(T==NULL) return(0);
else if (T->lchild==NULL && T->rchild==NULL) return(1);
else
{
num1=nodes(T->lchild);
num2=nodes(T->rchild);
return(num1+num2+1);
}
}

试卷A
一、选择题（本题共20分，每小题1分）

1．在数据结构中，从逻辑上可以把数据结构分成 （ ） 。
A．动态结构和静态结构 B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构 D. 内部结构和外部结构
2．线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( ) 。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续不连续都可以
3．不带头结点的单链表 head 为空的判定条件是( ) 。
A. head == NULL B. head->next ==NULL
C. head->next == head D. head! = NULL
4．在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入s 结点，则执行( ) 。
A. s-next=p-next; p-next=s; B. p->next=s->next; s-next=p;
C. q->next=s; s->next=p; D. p-next=s; s->next=q;
5．从一个具有n个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较( )个结点。
A. n B. n/2
C. (n-1)/2 D. (n+1)/2
6．一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是( )。
A. edcba B. decba C. dceab D. abcde
7．判定一个循环队列 QU（最多元素为 m0）为满队列的条件是( )。
A. QU->front==QU->rear B. QU->front!=QU->rear
C. QU->front==(QU->rear+1) % m0 D. QU->front!=(QU->rear+1) % m0
8．栈和队列的共同点是( ) 。
A. 都是先进后出 B. 都是先进先出
C. 只允许在端点处插入和删除元素 D. 没有共同点
9．数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( ) 。
A. SA+141 B. SA+144
C. SA+222 D. SA+225
10．广义表((a，b)，c，d)的表尾是( )。
A. a B. b
C. (a，b) D. (c，d)
11．设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组 B[1，n(n-1)/2]中，对下三角部分中任一元素 ai,j(i≥j)，在一维数组 B 的下标位置k的值是（ ）。
A. i(i-1)/2+j-1 B. i(i-1)/2+j
C. i(i+1)/2+j-1 D. i(i+1)/2+j

13. 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是（ ）。
A. acbed B. decab C. deabc D. cedba
12. 如下图所示的 4 棵二叉树中，（ ）不是完全二叉树。

14. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。
A. 3 B. 4
C. 5 D. 6
15. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（ ）。
A. 2h B. 2h-1
C. 2h+1 D. h+1
16．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ） 倍。
A. 1/2 B. 1 C. 2 D. 4
17．在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（ ）条边。
A. n B. n+1
C. n-1 D. n/2
18．已知一有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 （ ）。

A. v1，v2，v3，v5，v4 B. v1，v2，v3，v4，v5
C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2
19. 采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为（ ）。
A. n B. n/2
C. (n+1)/2 D. (n-1)/2
20．快速排序方法在（ ）情况下最不利于发挥其长处。
A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值
C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数
二、填空题（本题共20分，每空1分）

1．根据数据元素之间的不同特征，通常有四类基本结构：_____、______、______和______。
2．下面程序段的时间复杂度是：______。
for (i=0；i<n；i++)
for (j=0；j<m；j++)
A[i][j]=0；
3．向一个长度为 n 的线性表中的第 i 个元素（1≤i≤n）之前插入一个元素时，需向后移动______个元素。
4．在一个单链表中的 p 所指结点之前插入一个 s 所指结点时，可执行如下操作：
（1）s->next=______ ;
（2）p-next=s;
（3）t=p->data;
（4）p->data= ______;
（5）s->data= ______;
5. 深度为 k 的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是 。
6. 一个广义表为（a，（a，b），d，e，（（i，j），k）），则该广义表的深度为________。
7. 有一棵树如下图所示，回答下面的问题：结点 k3 的度是 ； 这棵树的度为 ；这棵树的深度是 。

8．在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第 七 个记录 60 插入到有序表时，为寻找插入位置需比较______次。
9. 队列的插入操作在_______进行，删除操作在_______进行。
10. 判定一个有向图中是否存在回路，即是否含有环，可以使用_________方法。

三、阅读程序写结果（本题共20分，每小题5分）

1． 单链表中，指针p指向某结点，执行以下操作后，请用一句话描述程序执行的结果是什么？
q=p->next;
p->data=p->next->data;
p->next= p->next->next;
free(q);
2． 阅读下面二分查找程序代码，填充空白位置，使算法完整。
int BinSearch (SeqList R, KeyType k)
{ int low=1,high=n,mid;
while(low<=high)
{ mid=(low+high)/2;
if(R[mid].key==k) return mid;
if(R[mid].key>k) ____①____;
else ______②_____; }
return 0;
}
3． 如下图所示给出了图 G 及对应的邻接表，根据给定的 dfs 算法，从顶点 8 出发，写出其搜索序列。
Adjlist gl;
void dfs(int v)
{ struct vexnode *p;
printf("%d"，v);
visited[v]=1;
p=gl[v]->link; /* gl 是该图的邻接表的表头指针数组 */
while (p!=NULL)
{ if (visited[p->adjvex]==0) dfs(p->adjvex);
p=p->next; }
}

4． 二叉树采用二叉链表存储结构，将第四题综合题3中的二叉树，运行下面的递归算法，请写出最后的返回结果是什么？
int count (btree *b)
{ int num1，num2;
if (b==NULL) return(0);
else if (b->left==NULL && b->right==NULL) return (1);
else { num1=count (b->left);
num2=count (b->right);
return (num1+num2); }
}
四、综合题（本题共30分，每小题5分）
1. 有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为{ 4、7、5、2、9}，试画出对应的哈夫曼树（注意：构造哈夫曼树过程中请按左子树根结点的权值小于等于右子树根结点的权值次序构造），并求出每个字符的哈夫曼编码。
2. 利用普里姆算法，从节点1出发构造出如下图所示的图 G 的一棵最小生成树。

3. 一棵二叉树如下面的图所示，要求：
（1）写出对此二叉树进行中序遍历时得到的结点序列。
（2）画出由此二叉树转换得到的森林。

4．请画出，将元素3和元素6依次插入到下图所示的平衡二叉树中的结果，要求仍然保持为一棵平衡二叉树。

5. 一组元素为（46，25，78，62，12，37，70，29），要求：
（1）画出按元素排列顺序输入生成的一棵二叉排序树。
（2）画出在二叉排序树中，删除元素46后的结果
6. 设哈希表长度为11，哈希函数h(key)=key % 11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的哈希表。并计算在查找成功时候的平均查找长度。
五、算法题（本题共10分）
假设线性表中包含n个数据元素，请写出顺序存储方式下对n个元素的冒泡排序算法。具体存储结构如下：
#define Maxsize 20
Typedef int KeyType;
Typedef struct {
KeyType key; //关键字项
InfoType otherinfo; //其它数据项
} RedType; //记录类型
Typedef struct {
RedType r[Maxsize+1]; //r[0]闲置或者用做哨兵单元
Int length; //顺序表长度
} SqList; //顺序表类型

参考答案
一、 选择题（本题共20分,每题1分）
1
2
3
4
5
6
7
8
9
10
C
D
A
C
D
C
C
C
C
D
11
12
13
14
15
16
17
18
19
20
B
D
C
C
B
B
C
C
C
C

二、填空题（本题共20分，每空1分）
1. 集合、线性结构、树形结构、网状结构
2. O(m*n)
3. n-i+1
4. ① p->next ② s->data ③ t
5. ① 2 ② 2-1 ③ 2+1
6. 3层
7. ① 2 ② 3 ③ 4
8. 3
9. 队尾、对头
10. 拓扑排序

三、阅读程序写结果（本题共20分，每小题5分
1. 删除了p结点
2. high=mid-1; low= mid+1;
3. 搜索序列为：8，4，2，1，3，6，7，5。
4. 返回结果是2

四、综合题（本题共30分，每小题5分）

1. 解：依题意，各字符对应的哈夫曼编码以及相应的哈夫曼树结果如下：
a：011 b：10 c：00 d：010 e：11

2. 解：使用普里姆算法构造棵最小生成树的过程如图所示

3. 中序遍历的结果是：DEFBAC。 转换的森林如图所示：

4. 最终结果如图：

5. 46删除之前和删除之后的两个结果分别如下图所示

6. H(1)=1
H(13)=2
H(12)=1 冲突 ， H1=2 冲突， H2=3
H(34)=1 冲突 ， H1=2 冲突， H2=3 冲突， H3=4
H(38)=5
H(33)=0
H(2)=2 冲突，H1=3 冲突，H2=4 冲突，H3=5 冲突，H4=6
H(22)=0 冲突，H1=1冲突，H2=2 冲突，H3=3 冲突，H4=4 冲突，H5=5冲突，H6=6冲突，H7=7

ASL=(1+1+3+4+1+1+5+8)/8=24/8=3

五、算法题（本题共10分）
void BubbleSort (SeqList R)
{ int i,j； Boolean exchange;
For( i=1;i<n;i++)
{exchange=false;
for(j=1;j<=n-I;j++)
if(R[j+1].key<R[j].key)
{R[0]=R[j+1]; R[j+1]=R[j] ; R[j]=R[0];
exchange=true;}
if (!exchange) return;
}
}
A
B ∧ NULL
∧ C ∧
ROOT
∧ D
E
∧ F ∧
∧ G ∧
A
C
D
E
F
G
A
C
D
E
F
G
A
B ∧ NULL
∧ C ∧
ROOT
∧ D
E
∧ F ∧
∧ G ∧