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

数据结构模拟试题10一、单项选择题（每题 3 分，共30分）1设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。(A) 2n(B) n(C) n/2(D) n(n-1)2设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。(A) n(B) n-1(C) 2n(D) 2n-13设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。(A) 40，42，60，55，80，85(B) 42，45，55，60，85，80(C) 42，40，55，60，80，85(D) 42，40，60，85，55，804（ ）二叉排序树可以得到一个从小到大的有序序列。(A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历5设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-16程序段s=i=0；do i=i+1； s=s+i；while(i<=n)；的时间复杂度为（ ）。(A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(n3/2)7设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。(A) head=0 (B) head->next=0(C) head->next=head(D) head!=08设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ ）。(A) 20(B) 256(C) 512(D) 10249设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。(A) 1(B) 2(C) 3(D) 410.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。(A) top=top+1;(B) top=top-1;(C) top->next=top; (D) top=top->next;二、填空题（每题2分，共20分）1. 设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_=p；s->right=p->right；_=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。2. 设完全有向图中有n个顶点，则该完全有向图中共有_条有向条；设完全无向图中有n个顶点，则该完全无向图中共有_条无向边。3. 设关键字序列为(Kl，K2，Kn)，则用筛选法建初始堆必须从第_个元素开始进行筛选。4. 解决散列表冲突的两种方法是_和_。5. 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有_个。6. 高度为h的完全二叉树中最少有_个结点，最多有_个结点。7. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是_。8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是_。9. 设一棵二叉树的前序序列为ABC，则有_种不同的二叉树可以得到这种序列。10. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。struct record int key;datatype others;void quickpass(struct record r, int s, int t, int &i) int j=t; struct record x=rs; i=s; while(i<j) while (i<j && rj.key>x.key) j=j-1; if (i<j) ri=rj;i=i+1; while (_) i=i+1; if (i<j) rj=ri;j=j-1; _;三、判断题（每题 2 分，共20分）1不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ）2当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）3设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）4完全二叉树中的叶子结点只可能在最后两层中出现。（ ）5哈夫曼树中没有度数为1的结点。（ ）6对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ）7先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ）8由树转化成二叉树，该二叉树的右子树不一定为空。（ ）9线性表中的所有元素都有一个前驱元素和后继元素。（ ）10.带权无向图的最小生成树是唯一的。（ ）四、算法设计题（每题10分，共30分）1. 设计在链式结构上实现简单选择排序算法。2. 设计在顺序存储结构上实现求子串算法。3. 设计求结点在二叉排序树中层次的算法。3数据结构模拟试题10参考答案一、单项选择题（每题 3 分，共30分）1B2B3C4B5B6A7C8C9B10D二、填空题（每小题2分，共20分）1. s->left=p，p->right2. n(n-1)，n(n-1)/23. n/24. 开放定址法，链地址法5. 146. 2h-1，2h-17. (12，24，35，27，18，26)8. (12，18，24，27，35，26)9. 510. i<j && ri.key<x.key，ri=x三、判断题（每题 2分，共20分）1对2对3对4对5对6对7对8错9错10错四、算法设计题（每题10分，共30分）1. 设计在链式结构上实现简单选择排序算法。void simpleselectsorlklist(lklist *&head) lklist *p,*q,*s; int min,t; if(head=0 |head->next=0) return; for(q=head; q!=0;q=q->next) min=q->data; s=q; for(p=q->next; p!=0;p=p->next) if(min>p->data)min=p->data; s=p; if(s!=q)t=s->data; s->data=q->data; q->data=t; 2. 设计在顺序存储结构上实现求子串算法。void substring(char s , long start, long count, char t ) long i,j,length=strlen(s); if (start<1 | start>length) printf("The copy position is wrong"); else if (start+count-1>length) printf("Too characters to be copied");else for(i=start-1,j=0; i<start+count-1;i+,j+) tj=si; tj= '0'3. 设计求结点在二叉排序树中层次的算法。int lev=0;typedef struct nodeint key; struct node *lchild,*rchild;bitree;void level(bitree *bt,int x) if (bt!=0)lev+; if (bt->key=x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);数据结构模拟试题11一、单项选择题（每题 3 分，共30分）1. 字符串的长度是指（ ）。(A) 串中不同字符的个数(B) 串中不同字母的个数(C) 串中所含字符的个数(D) 串中不同数字的个数2. 建立一个长度为n的有序单链表的时间复杂度为（ ）(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)3. 两个字符串相等的充要条件是（ ）。(A) 两个字符串的长度相等(B) 两个字符串中对应位置上的字符相等(C) 同时具备(A)和(B)两个条件(D) 以上答案都不对4. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。(A) 99(B) 97(C) 91(D) 935. 在二叉排序树中插入一个关键字值的平均时间复杂度为（ ）。(A) O(n)(B) O(1og2n)(C) O(nlog2n)(D) O(n2)6. 设一个顺序有序表A1:14中有14个元素，则采用二分法查找元素A4的过程中比较元素的顺序为( )。(A) A1，A2，A3，A4(B) A1，A14，A7，A4(C) A7，A3，A5，A4(D) A7，A5 ，A3，A47. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。(A) 8(B) 7(C) 6(D) 58. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ ）个度数为0的结点。(A) 5(B) 6(C) 7(D) 89. 设无向图G中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。(A) aedfcb(B) acfebd(C) aebcfd(D) aedfbc10. 队列是一种（ ）的线性表。(A) 先进先出(B) 先进后出(C) 只能插入(D) 只能删除 二、填空题（每题2分，共20分）1 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_。2 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。typedef struct nodeint data;struct node *lchild;struct node *rchild;bitree;void bstinsert(bitree *&t,int k)if (t=0 ) _;t->data=k;t->lchild=t->rchild=0;else if (t->data>k) bstinsert(t->lchild,k);else_;3 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _;。4 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_和head=_（设结点中的两个指针域分别为llink和rlink）。5 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为_。6 完全二叉树中第5层上最少有_个结点，最多有_个结点。7 设有向图中不存在有向边<Vi,Vj>，则其对应的邻接矩阵A中的数组元素Aij的值等于_。8 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_。9 设连通图G中有n个顶点e条边，则对应的最小生成树上有_条边。10 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与_相互交换即可。三、判断题（每题 2 分，共20分）1. 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（ ）2. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ）3. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（ ）4. 二维数组和多维数组均不是特殊的线性结构。（ ）5. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ）6. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ）7. 非空的双向循环链表中任何结点的前驱指针均不为空。（ ）8. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（ ）9. 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（ ）10. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ ）四、算法设计题（每题15分，共30分）1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。7数据结构模拟试题11参考答案一、单项选择题（每题 3 分，共30分）1C2C3C4B5B6C7B8C9A10A二、填空题（每小题2分，共20分）1. (49，13，27，50，76，38，65，97)2. t=(bitree *)malloc(sizeof(bitree)，bstinsert(t->rchild,k)3. p->next=s4. head->rlink，p->llink5. CABD6. 1，167. 08. (13，27，38，50，76，49，65，97)9. n-110. 50三、判断题（每题 2分，共20分）1对2错3对4错5错6对7对8对9对10对四、算法设计题（每题15分，共30分）1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt->lchild,count); countnode(bt->rchild,count);2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct int vertexm; int edgemm;gadjmatrix;typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode;typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1 ,glinkheadnode g2 )int i,j; glinklistnode *p;for(i=0;i<=n-1;i+) g2i.firstarc=0;for(i=0;i<=n-1;i+) for(j=0;j<=n-1;j+)if (g1.edgeij=1)p=(glinklistnode *)malloc(sizeof(glinklistnode);p->adjvertex=j;p->nextarc=gi.firstarc; gi.firstarc=p;p=(glinklistnode *)malloc(sizeof(glinklistnode);p->adjvertex=i;p->nextarc=gj.firstarc; gj.firstarc=p;数据结构模拟试题12一、填空题（每小题2分，共18分）1、 数据的逻辑结构包括 ， 和 三种结构。2、 算法分析的两个主要方面是 和 。3、 在双向链表中，每个结点有两个指针域，一个指向 ，另一个指向 。4、 空串是 ，其长度等于 。5、 有一个10阶对称矩阵A，采用压缩存储方式，以行为主存储下三角形到一个一维数组中，若A00的地址是200（每个元素占2个基本存储单元），则A95的地址是 。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(n2n)2、 设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则向S中压入一个元素P执行的操作是（ ）。（A） Stop+=p； （B） S+top=p；(C) S-top=p； （D） Stop-=p； 3、 稀疏矩阵一般的压缩存储方法有主要有（ ）两种。（A） 二维数组和三维数组 （B） 三元组和散列（C） 三元组和十字链表 （D） 散列和十字链表4、 一般树的存储结构主要有（ ）。（A） 双亲表示法，孩子表示法，链表表示法（B） 双亲表示法，孩子表示法，孩子兄弟表示法（C） 双亲表示法，孩子兄弟表示法，链表表示法（D） 双亲表示法，孩子兄弟表示法，链表表示法5、 一棵有n(n0)个结点的满二叉树的叶子结点的数目是 ，非叶子结点的数目是 。（ ）（A） 22n 22n （B） 22n-1 22n （C） 22n-1 22n-1 （D） 22n 22n-16、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍，所有顶点的度之和等于所有顶点的入度之和的 倍。（ ）（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，47、设有一个长度为12的有序表，采用二分查找方法对该表进行查找时，在表内各元素等概率情况下查找成功所需的平均比较次数为。（ ）(A) 35/12 （B） 37/12 （C） 39/12 （D） 43/128、 设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（ ）。（A） 25，28，37，14，56，80，60，50 （B） 25，28，37，14，60，80，56，50 （C） 25，28，14，37，60，80，56，50 （D） 25，28，14，37，60，56，80，509、 文件在外存上的上的组织方式称为文件的物理结构。基本的物理结构有：（ ）(A) 顺序结构，链接结构，线性结构 (B) 线性结构，链接结构，索引结构(C) 顺序结构，链接结构，线性结构 (D) 顺序结构，链接结构，索引结构三、分析题（每题6分，共30分）1、 设有一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，请画出这棵二叉树，然后画出其后序线索化树。2、 对于下图中的网，写出该网的邻接链表；然后写出其广度优先搜索生成树（假设从顶点V1出发）；最后给出按Prime算法从顶点V5出发得到的最小生成树。1524389113341373、 将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除18之后的二叉排序树T1；最后再画出插入18之后的二叉排序树T2。4、 线性表的关键字集合71，25，8，29，42，69，95，33，17，56，47，共有11个元素，已知散列函数为：H（k） = k MOD 11，采用链地址处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。5、 已知序列35，29，52，60，17，9，38，27，13，45，请给出采用归并排序法对该序列做非递减排序时的每一趟结果。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的队首元素出队操作算法。#define Max_Queue_Size 100ElemType Delete_CirQueue(SqQueue Q) ElemType x ; if ( ) printf(“The Circular Queue is Null!”) ;else x=Q.Queue_arrayQ.front ; ; 2、 二叉树中序遍历的非递归算法。#define Max_Node_Num 50Void InorderTraverse( BTNode *T) BTNode *StackMax_Node_Num ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“The Binary Tree is Empty!n”) ; else do while (p!=NULL) stack+top=p ; p=p->Lchild ; if (top=0) bool=0 ; else ; visit( p->data ) ; ; while ( ) ; 3、 折半查找算法。int Bin_Search(SSTable ST , KeyType key) int Low=1，High=ST.length, Mid ; while (Low<High) ; if (ST. elemMid.key=key) return(Mid) ; else if (ST. elemMid.key<key) Low=Mid+1 ;else High=Mid-1 ; ; 4、 简单选择排序算法。void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1;m<L->length;m+) k=m ; for (n=m+1;n<=L->length;n+) if ( ) k=n ; if ( ) L->R0=L->Rm; L->Rm=L->Rk; ; 五、编写算法（要求给出相应的数据结构说明，14分）将以L为头结点的单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同；并对算法进行分析。19数据结构模拟试题12参考答案一、填空题（每小题2分，共18分）1、 线性结构 树形结构 图（或网）状结构2、 时间复杂度 空间复杂度3、 (直接)前驱结点 (直接)后继结点4、 零个字符组成的串 0 5、 3006、 只有右子树上的所有结点7、 先序遍历8、 索引 块9、 操作系统 数据库二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）题号123456789答案ABCBDBBCD三、分析题（每题6分，共30分）fabcehidgNULLfabcehidg图(a) 二叉树图(b) 后序线索化树1、 解：所画出的二叉树如图(a)所示。树的后序遍历序列是gdhiebfca，其后序线索化树如图(b)所示。2、 解：该网的邻接链表如下图所示：0123412345293758193441351124174321333532114318从顶点V1出发的广度优先搜索的顶点序列是12354，相应的生成树如下：1524389137从顶点V1出发广度优先搜索生成树从顶点V5出发的最小生成树1524333473、 解：将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中所得到的二叉排序树T如图(a)所示；删除18之后的二叉排序树T1如图(b)所示；最后再插入18之后的二叉排序树T2。149197134256图(b) 删除18的二叉排序树14918713419256图(a) 生成的二叉排序树14919713418256图(c) 插入18后的二叉排序树4、 解：根据所给定的散列函数和处理冲突方法，得到的散列表结构如下：0123456789103356 25477117 298 4295 69成功查找的平均查找长度：ASL=(1×8+2×2+3×1)/11=17/115、 解：做非递减排序时的每一趟结果如下：初始关键字：35，29，52，60，17，9，38，27，13，45第一趟： 29，35 52，60 9，17 27，38 13，45第二趟： 29，35，52，60 9，17，27，38 13，45第三趟： 29，35，52，60 9，13，17，27，38，45第四趟： 9，13，17，27，29，35，38，45，52，60第四趟归并完毕，排序结束。四、算法填空（每空2分，共20分）请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。1、 循环队列Q的队首元素出队操作算法。Q.front=Q.rearQ.front=(Q.front+1)%Max_Queue_Size ;2、 二叉树中序遍历的非递归算法。p=stacktop-p=p->Rchildbool!=0 3、 折半查找算法。Mid=(Low+High)/2return(0)4、 简单选择排序算法。L->Rn.key<L->Rk.keyk!=mL->Rk=L->R0五、编写算法（要求给出相应的数据结构说明，14分）解：结点类型定义及算法如下：#define int ElemType typedef struct Lnode ElemType data; /* 数据域，保存结点的值 */struct LNode *next; /* 指针域 */LNode; /* 结点的类型 */void Delete_LinkList_Value(LNode *L) LNode *p=L->next, *q, *ptr ;ElemType k ;while ( p->next!=NULL) k=p->data ; ptr=p ; q=ptr->next ;while (q!=NULL) if (q->data=k) ptr->next=q->next ; free(q) ; /* 删除值相同的结点 */ptr=ptr>next ; q=ptr>next ; /* 继续检查后续结点 */p=p->next ; /* 继续检查下一结点，是否有值相同的结点 */算法分析：设单链表长度为n，若指针p指向第i(i1,n-1)个结点，则删除和指针p所指向结点值相同的结点时：比较次数为n-i，指针的移动次数为n-i，则总的比较次数为：i=1(n-i)=n(n-1)/2n-1所以，时间复杂度为：O(n2)