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

数据结构模拟试题13一、填空题（每小题2分，共18分）1、 数据的逻辑结构包括 ， 和 三种结构。2、 队列是操作受限的线性结构，只能在 插入元素，而在 删除元素。3、 串是一种特殊的线性表，其特殊性体现在 。4、 有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形到一个一维数组中，A00的地址是100（每个元素占2个基本存储单元），则A59的地址是 。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(n2n)2、 设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（ ）。（A） p=Stop+； （B） p=S+top；(C) p=Stop-； （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） gdheibfca5、 具有五层结点的平衡二叉树至少有 。（ ）（A） 10 （B） 12 （C） 17 （D） 156、 在无权图G的邻接矩阵中，若(Vi,Vj)或属于G的边集，则对应元素Aij等于 ，否则等于 。（ ）（A） 1，1 （B） 1，0 （C） 0，1 （D） 0，07、 判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ）。(A) 广度优先遍历算法 (B) 求关键路径的方法(C) 深度优先遍历算法 (D) 求最短路径的Dijkstra算法8、设有一个长度为n的线性表，当采用顺序查找方法时，每个元素的平均查找长度是 ；而采用二分查找方法时，其平均查找长度是 。（ ）(A) n/2 ,O(n) （B） n/2,O(2n) （C） (n+1)/2, O(n2n) （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算法得到的最小生成树。1243812561173、 将关键字序列（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 100Void Insert_CirQueue(SqQueue Q , ElemType e) if ( ) printf(“The Circular Queue is Overflow!”) ;else ; Q.Queue_arrayQ.rear=e ; 2、 二叉树先序遍历的非递归算法。#define Max_Node_Num 50Void PreorderTraverse( BTNode *T) BTNode *StackMax_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中，统计图中顶点的入度。链表结点adjvexinfonextarc顶点结点indegreedatafirstarcVoid count_indegree(ALGraph *G) int k ; LinkNode *p ;for (k=0; kvexnum; k+)G-adjlistk.indegree=0 ;for (k=0; kvexnum; k+) ;while (p!=NULL) G-adjlistp-adjvex.indegree+ ; ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,k ,flag ;for (j=0; jlength; j+) ;for (k=1; klength-j; k+) /* 一趟排序 */if ( ) flag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; ; if (flag=TRUE) break ; 五、编写算法（要求给出相应的数据结构说明，14分）设以L为头结点的单链表中的所有结点的值均互不相同。对该单链表进行动态查找，查找值为k的结点：若链表中有该值的结点，则删除；若链表中没有该值的结点，则插入为第一个结点；并对算法进行分析。5数据结构模拟试题13参考答案一、填空题（每小题2分，共18分）1、 线性结构 树形结构 图（或网）状结构2、 表的一端 表的另一端3、 数据元素是一个字符4、 2005、 2h-16、 n 2e7、 以顺序方式存储 结点按关键字有序8、 索引 散列9、 归并 内、外存之间的数据交换二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ACBCDBCDA三、分析题（每题6分，共30分）1、 解：依题意对应的Huffman树如下图所示。39891772354691322WPL=(2+3)4+(4+6+7)3+(8+9)2=1052、 解：该网的邻接链表如下图所示： 012312342123748112364112617451821135从顶点V3出发的深度优先搜索的顶点序列是3214，相应的生成树如下：最小生成树1243567从顶点V3出发深度优先搜索生成树124381263、 解：将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除13之后的二叉排序树T1如图(b)所示；最后再插入13之后的二叉排序树T2。图(a) 生成的二叉排序树14719913416251218图(b) 删除13的二叉排序树147199124162518图(c) 插入13的二叉排序树147199124162518134、 解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：H(31)=31 MOD 11=9 H(25)=25 MOD 11=3 H(18)=18 MOD 11=7H(19)=19 MOD 11=8 H(42)=42 MOD 11=9 冲突 H(42)=(9+1) MOD 11=10H(67)=67 MOD 11=1 H(15)=15 MOD 11=4 H(33)=33 MOD 11=0H(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 1033 67 46 25 15 36 17 18 19 31 42成功查找的平均查找长度：ASL=(19+12+13)/11=14/115、 解：做非递减排序时的每一趟结果如下：初始关键字：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.frontQ.rear=(Q.rear+1)%Max_Queue_Size ;2、 二叉树先序遍历的非递归算法。P=p-Lchildp=stacktop-p!=NULL 3、统计图中顶点的入度。P=G-adjlistk.firstarcP=p-nextarc4、冒泡排序算法。flag=TRUEL-Rk.keyL-Rk+1.keyL-Rk+1=L-R0五、编写算法（要求给出相应的数据结构说明，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、 设有一个二维数组A0909，若每个元素占5个基本存储单元，A00的地址是1000，若按行优先（以行为主）顺序存储，则A68的存储地址是 。6、 二叉树由根结点， 和 三个基本单元组成。7、 若采用邻接矩阵存储一个图所需要的存储单元取决于图的 ；无向图的邻接矩阵一定是 。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； （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） 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） 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，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 ; ； pdata=data; ； headnext=p ; return (head); 2、按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入结点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 *)malloc(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) 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-Rk ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if ( ) break ; 五、编写算法（要求给出相应的数据结构说明，14分）设T是指向二叉树根结点的指针变量，用非递归方法统计树中度为1和度为0的结点个数。16数据结构模拟试题14参考答案一、填空题（每小题2分，共18分）1、 线性结构 树形结构 图（或网）状结构2、 时间复杂度 空间复杂度3、 物理上的相邻 指针4、 操作受限 后进先出（先进后出） 5、 13406、左子树 右子树7、 顶点数 对称矩阵8、 顺序存储且有序 散列存储9、索引 散列二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案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，23）生成二叉排序树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的希尔排序法，做非递减排序时的每一趟结果如下：初始关键字：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)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 ( !(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=stackt