陕师大《数据结构》 1 2 3章测试题

DS一、二、三章测试

一、选择题（每题2分，共20分）

1、 若某线性表中最常用的操作是取第i个数据元素，则应采用( )存储方式最节

约时间。

A 单链表 B 双链表 C 单循环链表 D 顺序表

2、 在一个长度为n的顺序表的表尾插入一个元素，其渐进时间复杂度为( )。

A O(n) B O(1) C O(n2 ) D O(log2n)

3、 假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n C.(front-rear+1)％n

B.(rear-front)％n D.(rear-front+n)％n

4、 已知一个栈的入栈序列是1,2,3,…, n，其输出序列是p1,p2,…,pn。若p1=n，则pi(1≤i≤n)为（ ）。

A. i B. n-i C. n-i+1 D. 不确定

5、下列程序段的时间复杂度为( ) s=0；

for(i=1；i

for(j=1；j

s+=i*j；

B.O(n) C.O(2n)

D.O(n2)

A.O(1)

6、假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是( )

A.head==NULL； B.head->next==NULL；

C.head!=NULL； D.head->next==head； 7、线性表是具有n个（ ）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项

8. 判定一个大小为m的栈S为满的条件是（ ）。

A. S.top- S.Base=0 B. S.top==0 C. S.top=m D. S.top-S.Base>=m 9、判定一个循环队列Q （最多元素为MAXSIZE）为满的条件是 。 A. Q.front= = Q.rear B. Q.front!=Q.rear

C. Q.front= =(Q.rear+1)%MAXSIZE D. Q.front!=(Q.rear+1)%MAXSIZE

10、带头结点的单链表（头指针为h）为空的判定条件是（ ）。 A. A. h=NULL B. h->next=NULL C. h->next=h D. H!=NULL

二、填空题（每题4分，共40分）

1、表长为n的顺序存储的线性表，假设搜索表中任何一个数据元素的概率相等，则搜索任何一个元素所需进行的平均比较次数为 。

2、 已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是： 。

3、 假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为 。

4、若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现 个不同的出栈序列。

5、已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是： 。

6、表长为n的顺序存储的线性表，假设搜索表中任何一个数据元素的概率相等，则搜索任何一个元素所需进行的平均比较次数为 。

7、 在一个单链表中删除p所指结点时，可以将p的后继结点的数据域放入p所指结点的数据域，然后将p的后继结点删除，那么，应执行以下操作：

q=p->next；

p->data= ； p->next= ；

8、将图1中s所指结点加到p所指结点之后，其语句应是 。

s e p

Ai-1 图1

Ai

9、若有程序段 i=0；s=0; while(s

三、程序设计（每题20分，共40分）

1、写一个算法，将一个不带头结点的单链表（由L指向）逆置。 提示：为方便起见，采用逆序创建新链表的方法放置逆置的结点，且新链表带头结点（由S指向）。

说明：该单链表的存储类型定义为 typedef int ElemType; typedef struct

{ ElemType data; LNode *next; } LNode, *LinkList; 函数模块的框架为：

void invertLinkList(LinkList L) {

请在此写入自己的算法 解答：

2、假设以带头结点的单链表表示线性表，单链表的类型定义如下： typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList;

编写算法，删除线性表中最大元素(假设最大值唯一存在)。

DS 1、2、3章测试答案

一、

DBDCD BCDCB 二、 1、(n+1)/2

2、s->next=p->next; p->next=s 3、10 4、5

5、s->next=p->next; p->next=s; 6、(n+1)/2

7、p->next->data 或 q->data； q->next 或 p->next->next 8、s->next=p-next； p->next=s 9、O(n)

10、O(log2n) 三、 1、

S=(LNode *)malloc(sizeof(LNode)); S->next=NULL; p=L; while(p) { Q=s->next; s->next=p; p=p->next; s->next->next=q;

} } 2、

void del_max_link (LinkList & head) {

pre=head; //pre是 p 的前驱 p=head->netx;

max_value=p->data; q=p;

while (q->next ) { if (q->next->data >max_value )

{

pre=q; p=q->next;

max_value=p->data;

}

q=q->next;

}// end of while; pre->next=p->next; delete p; }

6-9章 单元测试

一、选择题(每题2分，共10分)

1．在含有n个顶点的有向图G的邻接矩阵A[n][n]中，顶点 i 的入

度为( )。

A. i 行之和 B. A的上三角元素之和 C. i 列之和 D. A的下三角元素之和

2. 设哈希表长m=14, 哈希函数H(key)=key. 表中已有4个数据

元素15，38， 61， 84，他们的哈希地址分别是：addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7, 其余地址为空，如果采用二次探测再散列处理冲突，则关键字为48的数据元素在哈希表的存放地址是( )。

A. 9 B. 3 C. 5 D. 8

3. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均

相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( ) A.

4. 已知一个散列表如图所示，其散列函数为H(key)=key％11，采用

二次探查法处理冲突，则下一个插入的关键字49的地址为( ) A. 2 B. 3

0

1

2

3

15 38 61 84 4

5

6

7

8

9

10

C. 9

D. 1

39 15

B.49

15C.

51 15 D.

55 15

5. 下列所示各图中是中序线索化二叉树的是( )

二、填空题(每空2分，共20分)

1. 如图所示是一棵正在进行插入运算的平衡二叉树（AVL树），关键

码70的插入使它失去平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡，那么，调整后的AVL树是 。

2. 设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素

的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 ，按列优顺序存储，元素A[6,6]的存储地址为 。

3. 对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为

n2,则n0= 。

4. 深度为k的二叉树至多有 个结点。深度为k的完全二

叉树上至少有 个结点

5. 已知广义表A=（9,7,(8,10,(99)),12）,如果Head()和Tail()分别代表

求表头和表尾的操作，则

Head(Head(Tail(Tail(Head(Tail(Tail(A)))))))取出的是 。 6. 含有n个顶点的连通图至少有 条边。

7. 下面是在二叉排序树T中查找关键字之值为 key 的结点的算法。

如查找成功，p = 该结点的地址 ，返回TRUE。如查找不成功， p指向查找路径上访问的最后一个结并返回FALSE。指针f指向T的双亲，其初始调用值为 NULL。

Status SearchBST ( BiTree T，KeyType key， BiTree f，BiTree &p ) { if ( !T ) { p = f ; return FALSE; }

else if ( EQ( key, T ->data. key ) ) { p = T; return TRUE; } else if ( LT( key , T ->data. key ) )

return SearchBST ( ); else return

SearchBST ( ); }

三、简答题(每题10分，共70分)

1. 假设一棵二叉树的先序序列为EBADCFHGIKJ 和中序序列为

ABCDEFGHIJK。请画出该树。

2. 已知一有向图的邻接表存储结构如图3所示（V1存在1号单元中，

V5存在5号单元中），请画出该有向图，并根据有向图的深度优先遍历算法，从顶点V1出发，给出所得到的顶点序列。

V1 V2 V3 V4 V5 ^ ^ 3 2 4 ^

4 2 5 ^ 4 ^

3. 给出利用Prim算法构造出下图的一棵最小生成树，并画出构造过

程。

v1

6

11

1 5

5v

5 33

4 8v

3 7v

2

6

4. 假设某电文仅由A, B, C, D, E, F, G, H这8个字符组成。各个字符

在电文中出现的次数分别为6，14，4，7，9，16，28，8。请构造该赫夫曼树，并给出各字符的赫夫曼编码及该树的带权路径长度。

5. 对下面的AOE网，分别给出各个事件Vi(i=1,2,…,9)和各个活动ai

（i=1,2,…,11）的最早发生时间，最迟发生时间，并根据相应结构给出可能的关键活动和关键路径。

a1=66 V1V2a4=1V7a7=9V5a10=2a2=4 a5=1 a3=5 V3a8=7 a11=4 a9=4 V6V9V8V4a6=25 AOE网

6. 线性表的关键字集合｛87，25，310，08，27，132，68，95，187，

123，70，63，47｝，共有13个元素，已知散列函数为：H(k)=k % 13。 采用链地址法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。

7. （1）请画出与左图中二叉树对应的森林，并先序遍历森林。 （2）请画出右图所示的树所对应的二叉树。

参考答案

一、选择题 1. C 2. D 3. B 4. C 5. A

二、填空题 1. 如图

2. 352 232 3. n2+1 4. 2k-1 2k-1 5. 99 6. n-1 7. T -> lchild, key, T, p T -> rchild, key , T, p 三、简答题 1.

EBACDGFHIKJ

2. 1）根据邻接表给出的有向图如下：

V1 V2 V5V4 V3

2）从顶点V1出发，按照深度优先遍历算法给出的顶点序列为：V1, V3, V4, V5, V2

3. 生成树如下：

v1

1 v2

5 v3 v4

3 v5

4 v6

2

生成步骤如下列图a-e所示：

v1

v1

v1

v3

v3

v4

v6

v3

v6

图a 图b 图c

v1

v1

v2

v3 v4

v2

v3 v4

v5

v6

v6

图d 图e

4. 1）其赫夫曼树如下图所示：

35

19 10 16 92 57 28 15 29 14 9 4 6 7 8 2）各个字符的赫夫曼编码为：

A（6）：0011， B（14）：111， C（4）：0010， D（7）：1100 E（9）：000， F（16）：01， G（28）：10， H（8）：1101

3）带权路径长度为：

WPL=4*（4+6+7+8）+3*（9+14）+2*（16+28）=257 5.

顶点(事件) V1 V2 V3 V4 V5 V6 V7 V8 V9 ve 0 6 4 5 7 7 16 14 18 vl 0 6 6 8 7 10 16 14 18 活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e 0 0 0 6 4 5 7 7 7 16 14 l 0 2 3 6 6 8 7 7 10 16 14 l-e 0 2 3 0 2 3 0 0 3 0 0

关键活动为：a1，a4，a7，a8，a10，a11。

关键路径有两条：（V1,V2,V5,V7,V9）和(V1,V2,V5,V8,V9)

6. 依题意，得：

H（87）=87 ％ 13=9

H（25）=25 ％ 13=12 H(310) =310％13=11 H（08）=08 ％ 13=8 H（27）=27 ％13=1 H（132）=132=2 H（68）= 68 ％13= 3 H（95）=95 ％13=4 H（187）=187 ％13=5 H（123）=123 ％13=6 H（70）=70 ％13=5 H（63）=63 ％13=11 H（47）=47 ％13=8

采用链地址法处理冲突，所得链接表如右上图所示。 成功查找的平均查找长度：ASL=(1*10+2*3)/13=16/13 7.（1）

先序遍历森林序列为：EIJGBKACFD

（2）

1 2 3 4 6 8 5 7 8 2 对应二叉树

3 4 6 1 5

7

本文来源：https://www.bwwdw.com/article/jwfa.html