《数据结构》3套模拟试题综合测试题带答案5.doc

《数据结构》模拟试题13

一、填空题（每小题2分，共18分）
1、 数据的逻辑结构包括 ， 和 三种结构。
2、 队列是操作受限的线性结构，只能在 插入元素，而在 删除元素。
3、 串是一种特殊的线性表，其特殊性体现在 。
4、 有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形到一个一维数组中，A[0][0]的地址是100（每个元素占2个基本存储单元），则A[5][9]的地址是 。
5、 在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为 。
6、 对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的大小为
，邻接表中的结点总数为 。
7、 对线性表进行二分查找时，要求线性表必须是 ，且要求 。
8、 对于文件，按物理结构划分，可分为顺序文件、 文件、
文件和多关键字文件。
9、 外部排序的最基本方法是 ，其主要时间花费在 方面。
二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）
1、如下函数是求1!+2!+…+n!，其时间复杂度是（ ）。
Long int Sum (int n)
{ long int sum=0 , t=1 ; int p ;
for (p=1; p<=n ;p++) { t=t*p ; sum+=t ; }
return(sum) ;
}
（A） O(n) （B） O(n2) （C） O(㏒2n) （D） O(n㏒2n)
2、 设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（ ）。
（A） p=S[top++]； （B） p=S[++top]；
(C) p=S[top--]； （D） p=S[--top]；
3、 广义表((a),((b),c),(((d))))的表头是 ，表尾是 。（ ）
（A） (a) ((b),c),(((d))) （B） (a) (((b),c),(((d))))
（C） ((a),((b),c)),(((d))) （D） (a) (((d)))
4、一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，则其后序遍历序列是( )。
（A） abdgehicf （B） gdbheiafc
（C） gdhiebfca （D） gdheibfca
5、 具有五层结点的平衡二叉树至少有 。（ ）
（A） 10 （B） 12 （C） 17 （D） 15
6、 在无权图G的邻接矩阵中，若(Vi,Vj)或< Vi,Vj>属于G的边集，则对应元素A[i][j]等于 ，否则等于 。（ ）
（A） 1，1 （B） 1，0 （C） 0，1 （D） 0，0
7、 判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ）。
(A) 广度优先遍历算法 (B) 求关键路径的方法
(C) 深度优先遍历算法 (D) 求最短路径的Dijkstra算法
8、设有一个长度为n的线性表，当采用顺序查找方法时，每个元素的平均查找长度是 ；而采用二分查找方法时，其平均查找长度是 。（ ）
(A) n/2 ,O(n) （B） n/2,O(㏒2n)
（C） (n+1)/2, O(n㏒2n) （D） (n+1)/2, O(㏒2n)
9、 设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（ ）。
（A） 25，28，14，37，60，80，56，50 （B） 25，28，37，14，60，80，56，50
（C） 25，28，14，37，60，56，80，50 （D） 25，28，37，14，56，80，60，50

三、分析题（每题6分，共30分）
1、 设有一份电文中工使用了7个字符：a，b，c，d，s，m，n，它们出现的频率依次为3，6，4，2，8，9，7，请画出对应的Huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求其带权路径长度WPL。
2、 对于下图中的网，写出该网的邻接链表；然后写出其深度优先搜索生成树（假设从顶点V3出发）；最后给出按Kruskal算法得到的最小生成树。

1
2
4
3
8
12
5
6
11
7

3、 将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除13之后的二叉排序树T1；最后再后画出插入13之后的二叉排序树T2。

4、 线性表的关键字集合{31，25，18，29，42，67，15，33，17，36，46}，共有11个元素，已知散列函数为：H（k） = k MOD 11，采用线性探测法处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。

5、 已知序列{35，29，22，16，17，9，38，27，13，45}，请给出采用希尔排序法对该序列做非递减排序时的每一趟结果，增量序列为5，3，1。

四、算法填空（每空2分，共20分）
请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。
1、 循环队列Q的入队操作算法。
#define Max_Queue_Size 100
Void Insert_CirQueue(SqQueue Q , ElemType e)
{ if ( )
printf(“The Circular Queue is Overflow!”) ;
else { ;
Q.Queue_array[Q.rear]=e ; }
}

2、 二叉树先序遍历的非递归算法。
#define Max_Node_Num 50
Void PreorderTraverse( BTNode *T)
{ BTNode *Stack[Max_Node_Num] ,*p=T, *q ;
int top=0 ;
if (T==NULL) printf(“The Binary Tree is Empty!\n”) ;
else { do
{ visit( p-> data ) ; q=p->Rchild ;
if ( q!=NULL ) stack[++top]=q ;
;
if (p==NULL) ;
}
while ( ) ;
}
}

3、 用正邻接链表保存有向图，各结点的结构形式如下，所有的顶点结点放在数组adjlist[]中，统计图中顶点的入度。
链表结点
adjvex
info
nextarc
顶点结点
indegree
data
firstarc

Void count_indegree(ALGraph *G)
{ int k ; LinkNode *p ;
for (k=0; k<G->vexnum; k++)
G->adjlist[k].indegree=0 ;
for (k=0; k<G->vexnum; k++)
{ ;
while (p!=NULL)
{ G->adjlist[p->adjvex].indegree++ ; ; }
}
}

4、 冒泡排序算法。
#define FALSE 0
#define TRUE 1
Void Bubble_Sort(Sqlist *L)
{ int j ,k ,flag ;
for (j=0; j<L->length; j++)
{ ;
for (k=1; k<=L->length-j; k++) /* 一趟排序 */
if ( )
{ flag=FALSE ; L->R[0]=L->R[k] ;
L->R[k]=L->R[k+1] ; ; }
if (flag==TRUE) break ;
}
}

五、编写算法（要求给出相应的数据结构说明，14分）
设以L为头结点的单链表中的所有结点的值均互不相同。对该单链表进行动态查找，查找值为k的结点：若链表中有该值的结点，则删除；若链表中没有该值的结点，则插入为第一个结点；并对算法进行分析。

5

《数据结构》模拟试题13参考答案

一、填空题（每小题2分，共18分）

1、 线性结构 树形结构 图（或网）状结构
2、 表的一端 表的另一端
3、 数据元素是一个字符
4、 200
5、 2h-1
6、 n 2e
7、 以顺序方式存储 结点按关键字有序
8、 索引 散列
9、 归并 内、外存之间的数据交换

二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）
题号
1
2
3
4
5
6
7
8
9
答案
A
C
B
C
D
B
C
D
A

三、分析题（每题6分，共30分）
1、 解：依题意对应的Huffman树如下图所示。
39
8
9
17
7
2
3
5
4
6
9
13
22
WPL=(2+3)×4+(4+6+7)×3+(8+9)×2=105

2、 解：该网的邻接链表如下图所示：
0
1
2
3
1
2
3
4
2
12
3
7
4
8
∧
1
12
3
6
4
11
∧
2
6
1
7
4
5
∧
1
8
2
11
3
5
∧

从顶点V3出发的深度优先搜索的顶点序列是3→2→1→4，相应的生成树如下：
最小生成树
1
2
4
3
5
6
7
从顶点V3出发深度优先搜索生成树
1
2
4
3
8
12
6

3、 解：将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示；最后再插入13之后的二叉排序树T2。
图(a) 生成的二叉排序树
14
7
19
9
13
4
16
25
12
18
图(b) 删除13的二叉排序树
14
7
19
9
12
4
16
25
18

图(c) 插入13的二叉排序树
14
7
19
9
12
4
16
25
18
13

4、 解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：
H(31)=31 MOD 11=9 H(25)=25 MOD 11=3 H(18)=18 MOD 11=7
H(19)=19 MOD 11=8 H(42)=42 MOD 11=9 冲突 H(42)=(9+1) MOD 11=10
H(67)=67 MOD 11=1 H(15)=15 MOD 11=4 H(33)=33 MOD 11=0
H(17)=17 MOD 11=6
H(36)=36 MOD 11=3 冲突 H(36)=(3+1) MOD 11=4 冲突
H(36)=(4+1) MOD 11=5
H(46)=46 MOD 11=2
得到的散列表结构如下：
散列地址
关键字
0 1 2 3 4 5 6 7 8 9 10
33 67 46 25 15 36 17 18 19 31 42

成功查找的平均查找长度：ASL=(1×9+1×2+1×3)/11=14/11

5、 解：做非递减排序时的每一趟结果如下：
初始关键字：35，29，22，16，17，9，38，27，13，45
第一趟： 9，29，22，13，17，35，38，27，16，45
第二趟： 9，17，16，13，27，22，38，29，35，45
第三趟： 9， 13，16，17，22，27，29，35，38，45

第三趟归并完毕，排序结束。

四、算法填空（每空2分，共20分）
请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。
1、 循环队列Q的入队操作算法。
(Q.rear+1)%Max_Queue_Size==Q.front
Q.rear=(Q.rear+1)%Max_Queue_Size ;

2、 二叉树先序遍历的非递归算法。
P=p->Lchild
p=stack[top--]
p!=NULL

3、统计图中顶点的入度。
P=G->adjlist[k].firstarc
P=p->nextarc

4、冒泡排序算法。
flag=TRUE
L->R[k].key>L->R[k+1].key
L->R[k+1]=L->R[0]

五、编写算法（要求给出相应的数据结构说明，14分）
解：结点类型定义及算法如下：
#define int ElemType
typedef struct Lnode
{ ElemType data; /* 数据域，保存结点的值 */
struct LNode *next; /* 指针域 */
}LNode; /* 结点的类型 */
void Dynomic_search(LNode *L , ElemType k)
{ LNode *ptr , *p=L, *q=L->next ;
while ( q!=NULL&&q->data!=k)
{ p=q ; q=q->next ; }
if (q->data==k)
{ p->next=q->next ; free(q) ; } /* 若存在结点，则删除 */
else
{ ptr=(* LNode)malloc(sizeof(LNode)) ;
ptr->data=k ; ptr->next=L->next ; L->next=ptr ;
} /* 若结点不存在，插入新结点作为第一个结点 */
}

算法分析：设链表的长度为n，算法的时间主要耗费在移动指针q上，故时间复杂度为O(n)。

《数据结构》模拟试题14

一、填空题（每小题2分，共18分）
1、 对于给定的n个元素,可以构造出的逻辑结构有集合, ，
和 四种。
2、 数据结构中评价算法的两个重要指标是 和 。
3、 顺序存储结构是通过 表示数据元素之间的(逻辑)关系；链式存储结构是通过 表示数据元素之间的(逻辑)关系。
4、 栈是 的线性表，其操作数据的基本原则是 。
5、 设有一个二维数组A[0…9][0…9]，若每个元素占5个基本存储单元，A[0][0]的地址是1000，若按行优先（以行为主）顺序存储，则A[6][8]的存储地址是 。
6、 二叉树由根结点， 和 三个基本单元组成。
7、 若采用邻接矩阵存储一个图所需要的存储单元取决于图的 ；无向图的邻接矩阵一定是 。
8、 在查找时，若采用折半查找，要求线性表 ，而哈希表的查找，要求线性表 。
9、对于文件，按物理结构划分，可分为顺序文件、 文件、
文件和多关键字文件。

二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）
1、有如下递归函数fact(n)，其时间复杂度是（ ）。
Fact(int n)
{ if (n<=1) return 1;
else return(n*fact(n-1)) ;
}
（A） O(n) （B） O(n2) （C） O(㏒2n) （D） O(n㏒2n)
2、 以head为头结点的非空单循环链表的尾结点p的特点是（ ）。
（A） p->next=NULL； （B） p=NULL；
（C） p->next=head； （D） p=head；
3、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则从S中取出一个元素保存在P中执行的操作是（ ）。
（A） p=S[top++]； （B） p=S[++top]；
（C） p=S[--top]； （D） p=S[top--]；
4、 广义表(a, (a, b), d, e, ((i, j), k))的长度是 ，深度是 。（ ）
（A） 6，3 （B） 5，3 （C） 6，4 （D） 6，2
5、 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将(结点)数据存储在一维数组A[1…n]中时，数组中第i个结点的左子结点是 。（ ）
（A） A[2i](2i≤n) （B） A[2i+1](2i+1≤n)
（C） A[i/2] （D） 条件不充分，无法确定
6、设有一棵二叉树，其先序遍历序列是acdgehibfkj，中序遍历序列是dgcheiabkfj，则该二叉树的后序遍历序列是 。（ ）
（A） gdehickjfba （B） gdhiecfkjba
（C） dghieckjfba （D） gdhieckjfba
7、 在一个有向图中，所有顶点的出度之和等于所有顶点的入度之和的 倍，
所有顶点的度之和等于所有顶点的出度之和的 倍。（ ）
（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，4
8、设有一组记录的关键字为{19, 14, 23, 1, 68, 20, 84, 27}，用链地址法构造哈希表，哈希函数为H(key)=key MOD 13，哈希地址为1的链表中有 个记录。（ ）
(A) 4 （B） 2 （C） 3 （D） 1
9、 用直接插入法对下列四个序列按非递减方式排序，元素比较次数最少的是（ ）。
（A） 21，32，46，40，80，69，90，94 （B） 94，32，40，90，80，46，21，69
（C） 32，40，21，46，69，94，90，80 （D） 90，69，80，46，21，32，94，40

三、分析题（每题6分，共30分）
1、 若以{7, 19, 2, 6, 32, 3, 21, 10}作为叶子结点的权值，请构造对应的Huffman树，然后求出其带权路径长度WPL。

2、 对于下图中的网，写出该网的邻接链表；然后写出其广度优先搜索生成树（假设从顶点V1出发）；最后给出按Kruskal算法得到的最小生成树。
1
5
2
4
3
6
8
11
3
3
4
10
7

3、 将关键字序列（15，21，13，7，4，9，25，19，23）插入到初态为空的二叉排序树中，请画出建立二叉排序树T的过程；然后画出删除13之后的二叉排序树T1。

4、 线性表的关键字集合{71，25，8，29，42，69，95，33，17，56，47}，共有11个元素，已知散列函数为：H（k） = k MOD 11，采用链地址处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。

5、 已知序列{15，29，13，40，17，9，38，27，52，45}，请给出采用增量序列为5, 3, 1的希尔排序法，对该序列做非递减排序时的每一趟结果。

四、算法填空（每空2分，共20分）
请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。
1、头插入法创建单链表，以整数的最大值(32767)作为输入结束，链表的头结点head作为返回值。
LNode *create_LinkList(void)
{ int data; LNode *head, *p ;
head= (LNode *)malloc(sizeof(LNode)) ;
head->next=NULL; /*创建链表的表头结点head*/
while (1)
{ scanf(“%d”,& data) ;
if (data==32767) break ;
；
p–>data=data;
；
head–>next=p ;
}
return (head);
}

2、按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入结点i、结点ch。
#define Max_Node_Num 50
Typedef struct BTNode
{ char data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;

BTNode *Create_BTree()
{ BTNode *T , *p , *s[Max_Node_Num] ;
char ch ; int i , j ;
while (1)
{ scanf(“%d”,&i) ;
if (i==0) break ; /*以编号0作为输入结束*/
else { ch=getchar() ;
p=(BTNode *)malloc(sizeof(BTNode)) ;
p–>data=ch ;
;
s[i]=p ;
if (i==1) T=p ;
else
{ j=i/2 ; /* j是i的双亲结点编号 */
if ( ) s[j]->Lchild=p ;
else ;
}
}
}
return(T) ;
}

3、 图的邻接链表的结点结构如下图所示。下面算法是从顶点v出发，递归地深度优先搜索图G。
adjvex info nextarc
表结点
data firstarc
顶点结点

#define MAX_VEX_NUM 30 /* 最大顶点数 */
BOOLEAN Visited[MAX_VEX_NUM] ;
void DFS(ALGraph *G , int v)
{ LinkNode *p ;
Visited[v]=TRUE ;
Visit[v] ; /* 置访问标志，访问顶点v */
;
while (p!=NULL)
{ if (!Visited[p->adjvex]) ;
;
}
}

4、 冒泡排序算法。
#define FALSE 0
#define TRUE 1
Void Bubble_Sort(Sqlist *L)
{ int j ,k ,flag ;
for (j=0; j<L->length; j++) /* 共有n-1趟排序 */
{ flag=TRUE ;
for (k=1; k<=L->length-j; k++) /* 一趟排序 */
if ( )
{ flag=FALSE ; L->R[0]=L->R[k] ;
L->R[k]=L->R[k+1] ; L->R[k+1]=L->R[0] ; }
if ( ) break ;
}
}

五、编写算法（要求给出相应的数据结构说明，14分）
设T是指向二叉树根结点的指针变量，用非递归方法统计树中度为1和度为0的结点个数。

16

《数据结构》模拟试题14参考答案

一、填空题（每小题2分，共18分）
1、 线性结构 树形结构 图（或网）状结构
2、 时间复杂度 空间复杂度
3、 物理上的相邻 指针
4、 操作受限 后进先出（先进后出）
5、 1340
6、左子树 右子树
7、 顶点数 对称矩阵
8、 顺序存储且有序 散列存储
9、索引 散列

二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）

题号
1
2
3
4
5
6
7
8
9
答案
A
C
D
B
D
D
B
C
A

100
19
40
21
2
5
3
11
6
7
17
10
28
60
32
三、分析题（每题6分，共30分）
1、 解：所构造的Huffman树如下图所示。
WPL=(19+21+32)×2+(6+7+10)×4+(2+3)×5
=261

2、 解：该网的邻接链表如下图所示：
1
2
3
4
5
1
8
3
7
4
6
∧
0
8
2
4
3
10
4
11
∧
1
4
3
3
∧
1
10
2
3
0
7
4
3
∧
1
11
3
3
0
6
∧
0
1
2
3
4

从顶点V1出发的广度优先搜索的顶点序列是1→2→4→5→3，相应的生成树如下：
按Kruskal算法得到的最小生成树
1
5
2
4
3
6
3
3
4
从顶点V1出发广度优先搜索生成树
1
5
2
4
3
6
8
4
7

3、 解：将关键字序列（15，21，13，7，4，9，25，19，23）生成二叉排序树T的过程如图(a)所示；删除13之后的二叉排序树T1如图(b)所示。
15
21
15
13
21
15
7
13
21
15
4
7
13
21
15
9
4
7
13
21
15
25
9
4
7
13
21
15

图(a) 生成的二叉排序树T的过程
23
25
19
9
4
7
13
21
15
25
19
9
4
7
13
21
15

图(b) 删除13后的二叉排序树
25
23
19
4
7
9
21
15

4、 解：根据所给定的散列函数和处理冲突方法，得到的散列表结构如下：

0
1
2
3
4
5
6
7
8
9
10
∧
∧
∧
∧
33
∧
56

25
∧
47
∧
71
∧
17

29
∧
8
∧
42
∧
95

69

成功查找的平均查找长度：ASL=(1×8+2×2+3×1)/11=17/11
5、 解：采用增量序列为5, 3, 1的希尔排序法，做非递减排序时的每一趟结果如下：
初始关键字：15， 29， 13， 40， 52， 9，3 8， 27， 17， 45
第一趟： 9， 29， 13， 17， 45， 15， 38， 27， 40， 52
第二趟： 9， 27， 13， 17， 29， 15， 38， 45， 40， 52
第三趟： 9， 13， 15， 17， 27， 29， 38， 40， 45， 52

四、算法填空（每空2分，共20分）
请在下面各算法的空白处填上相应语句实现算法功能。每个空白处只能填一个语句。
1、头插入法创建单链表，以整数的最大值(32767)作为输入结束，链表的头结点head作为返回值。
P= (LNode *)malloc(sizeof(LNode))
p–>next= head–>next

2、按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入结点i、结点ch。
p–>Lchild=p–>Rchild=NULL
i%2==0
s[j]->Rchild=p

3、从顶点v出发，递归地深度优先搜索图G。
p=G->AdjList[v].firstarc
DFS(G, p->adjvex)
p=p->nextarc

4、 冒泡排序算法。
L->R[k].key>L->R[k+1].key
flag==TRUE

五、编写算法（要求给出相应的数据结构说明，14分）
解：结点类型定义及算法如下：
#define Max_Node_Num 50
Typedef struct BTNode
{ ElemType data ; /* 数据域，保存结点的值 */
struct BTNode *Lchild , *Rchild ; /* 指针域 */
}BTNode ; /* 结点的类型 */

Void count_node_num( BTNode *T)
{ BTNode *Stack[Max_Node_Num] ,*p=T, *q ;
int top=0 , leaf_num=0 , num1=0 ;
if (T==NULL) printf(“The Binary Tree is Empty!\n”) ;
else { do
{ if ( !(p->Lchild!=NULL&& p->Rchild!=NULL) )
{ if (p->Lchild==NULL&& p->Rchild==NULL) leaf_num++ ;
else num1++ ; }
q=p->Rchild ;
if ( q!=NULL ) stack[++top]=q ;
p=p->Lchild ;
if (p==NULL) { p=stack[t