《数据结构》模拟试题综合测试题带答案 (14)

1、数据结构模拟试题14一、填空题（每小题2分，共18分）1、 对于给定的n个元素,可以构造出的逻辑结构有集合, ， 和 四种。2、 数据结构中评价算法的两个重要指标是 和 。3、 顺序存储结构是通过 表示数据元素之间的(逻辑)关系；链式存储结构是通过 表示数据元素之间的(逻辑)关系。4、 栈是 的线性表，其操作数据的基本原则是 。5、 设有一个二维数组A0909，若每个元素占5个基本存储单元，A00的地址是1000，若按行优先（以行为主）顺序存储，则A68的存储地址是 。6、 二叉树由根结点， 和 三个基本单元组成。7、 若采用邻接矩阵存储一个图所需要的存储单元取决于图的 ；无向图的邻接矩阵一定

2、是 。8、 在查找时，若采用折半查找，要求线性表 ，而哈希表的查找，要求线性表 。9、对于文件，按物理结构划分，可分为顺序文件、 文件、 文件和多关键字文件。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、有如下递归函数fact(n)，其时间复杂度是（ ）。Fact(int n) if (nnext=NULL； （B） p=NULL；（C） p-next=head； （D） p=head； 3、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则从S中取出一个元素保存在P中执行的操作是（ ）。（A） p=Stop+； （B） p=S+top；（C） p=S-top；

3、 （D） p=Stop-； 4、 广义表(a, (a, b), d, e, (i, j), k)的长度是 ，深度是 。（ ）（A） 6，3 （B） 5，3 （C） 6，4 （D） 6，25、 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将(结点)数据存储在一维数组A1n中时，数组中第i个结点的左子结点是 。（ ）（A） A2i(2in) （B） A2i+1(2i+1n) （C） Ai/2 （D） 条件不充分，无法确定6、设有一棵二叉树，其先序遍历序列是acdgehibfkj，中序遍历序列是dgcheiabkfj，则该二叉树的后序遍历序列是 。（ ）（A） gdehickjfba （B

4、） gdhiecfkjba （C） dghieckjfba （D） gdhieckjfba7、 在一个有向图中，所有顶点的出度之和等于所有顶点的入度之和的 倍，所有顶点的度之和等于所有顶点的出度之和的 倍。（ ）（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，48、设有一组记录的关键字为19, 14, 23, 1, 68, 20, 84, 27，用链地址法构造哈希表，哈希函数为H(key)=key MOD 13，哈希地址为1的链表中有 个记录。（ ）(A) 4 （B） 2 （C） 3 （D） 19、 用直接插入法对下列四个序列按非递减方式排序，元素比较次数最少的是（ ）。（A）

5、 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算法得到的最小生成树。1524368113341073、 将关键字序列（15，21，13，7

6、，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分）请在下面各算法的空白处填上相应语句以实现算法功能。每个

7、空白只能填一个语句。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 ; ； pdata=data; ； headnext=p ; return (head); 2、按满二叉树的方式对结点

8、进行编号建立链式二叉树。对每个结点，输入结点i、结点ch。#define Max_Node_Num 50Typedef struct BTNode char data ; struct BTNode *Lchild , *Rchild ; BTNode ;BTNode *Create_BTree() BTNode *T , *p , *sMax_Node_Num ; char ch ; int i , j ; while (1) scanf(“%d”,&i) ; if (i=0) break ; /*以编号0作为输入结束*/ else ch=getchar() ; p=(BTNode *)ma

9、lloc(sizeof(BTNode) ; pdata=ch ; ; si=p ; if (i=1) T=p ; else j=i/2 ; /* j是i的双亲结点编号 */ if ( ) sj-Lchild=p ; else ; return(T) ; 3、 图的邻接链表的结点结构如下图所示。下面算法是从顶点v出发，递归地深度优先搜索图G。adjvex info nextarc表结点data firstarc顶点结点#define MAX_VEX_NUM 30 /* 最大顶点数 */BOOLEAN VisitedMAX_VEX_NUM ;void DFS(ALGraph *G , int v)

10、 LinkNode *p ; Visitedv=TRUE ; Visitv ; /* 置访问标志，访问顶点v */ ; while (p!=NULL) if (!Visitedp-adjvex) ; ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,k ,flag ; for (j=0; jlength; j+) /* 共有n-1趟排序 */ flag=TRUE ; for (k=1; klength-j; k+) /* 一趟排序 */ if ( ) flag=FALSE ; L-R0=L-R

11、k ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if ( ) break ; 五、编写算法（要求给出相应的数据结构说明，14分）设T是指向二叉树根结点的指针变量，用非递归方法统计树中度为1和度为0的结点个数。11数据结构模拟试题14参考答案一、填空题（每小题2分，共18分）1、 线性结构 树形结构 图（或网）状结构2、 时间复杂度 空间复杂度3、 物理上的相邻 指针4、 操作受限 后进先出（先进后出） 5、 13406、左子树 右子树7、 顶点数 对称矩阵8、 顺序存储且有序 散列存储9、索引 散列二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456

12、789答案ACDBDDBCA10019402125311671710286032三、分析题（每题6分，共30分）1、 解：所构造的Huffman树如下图所示。WPL=(19+21+32)2+(6+7+10)4+(2+3)5=2612、 解：该网的邻接链表如下图所示：1234518374608243104111433110230743111330601234从顶点V1出发的广度优先搜索的顶点序列是12453，相应的生成树如下：按Kruskal算法得到的最小生成树152436334从顶点V1出发广度优先搜索生成树1524368473、 解：将关键字序列（15，21，13，7，4，9，25，19，2

13、3）生成二叉排序树T的过程如图(a)所示；删除13之后的二叉排序树T1如图(b)所示。15211513211571321154713211594713211525947132115图(a) 生成的二叉排序树T的过程2325199471321152519947132115图(b) 删除13后的二叉排序树25231947921154、 解：根据所给定的散列函数和处理冲突方法，得到的散列表结构如下：0123456789103356 25477117 298 4295 69成功查找的平均查找长度：ASL=(18+22+31)/11=17/115、 解：采用增量序列为5, 3, 1的希尔排序法，做非递减

14、排序时的每一趟结果如下：初始关键字：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 *)mall

15、oc(sizeof(LNode)pnext= headnext2、按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入结点i、结点ch。pLchild=pRchild=NULL i%2=0sj-Rchild=p3、从顶点v出发，递归地深度优先搜索图G。p=G-AdjListv.firstarc DFS(G, p-adjvex) p=p-nextarc 4、 冒泡排序算法。L-Rk.keyL-Rk+1.key flag=TRUE五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#define Max_Node_Num 50Typedef struct BTNode ElemType data ; /* 数据域，保存结点的值 */struct BTNode *Lchild , *Rchild ; /* 指针域 */BTNode ; /* 结点的类型 */Void count_node_num( BTNode *T) BTNode *StackMax_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