数据结构专升本模拟题与参考答案

1/22作业题（一）一、单项选择题1.从逻辑上可以把数据结构分为（）两大类。．动态结构、静态结构B．顺序结构、链式结构．线性结构、非线性结构D．初等结构、构造型结构2.链表不具有的特点是（）．插入、删除不需要移动元素B．可随机访问任一元素．不必事先估计存储空间D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;．O(1)B．O(n)．O(n2)D．O(n3)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。．2B．3．4D．6、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是，则第6个元素的存储地址是（．98B．100．102D．106、判定一个栈s（最多元素为m0）为空的条件是（．s-〉top!=0B．s-〉top==0．s-〉top!=m0D．s-〉top==m0、循环队列用数组A[m]（下标从0到）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（rear-front+m）%mB．rear-front+1．rear-front-1D．rear-front、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（．连接B．求子串．模式匹配D．判子串、设串'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（．BCDEFB．BCDEFG．BCPQRSTD．BCDEFEF10、数组常用的两种基本操作是（．建立与查找B．删除与查找．插入与索引D．查找与修改二、填空题1.所谓稀疏矩阵指的是________且分布没有规律。2.队列是的线性表，其运算遵循________的原则。3.空格串是________________________________。4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。、设图G有n个顶点和e条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为，而对用邻接表表示的图进行深度或广度优先搜索遍历时的时间复杂度为，图的深度或广度优先搜索遍历时的空间复杂度均为。、一个图的表示法是唯一的，而表示法是不唯一的。三、算法设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中的一度结点数目。四、应用题、对关键字无序序列(36，25，，12，65，43，20，58)进行直接选择排序，请写出每一趟排序的结果。（10分）、对无向带权图，用克鲁斯卡尔算法构造最小生成树。（10分）A93208CBD5E6412GF3、已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况）、设被查找文件有4095个记录，对每个记录查找记录概率相等，若采用顺序查找，成功查找平均比较次数为多少？作业题（二）、单项选择题1.有六个元素6，，，，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.2341562.栈和队都是（）．顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构、顺序查找法适合于存储结构为（）的线形表。．散列存储．顺序存储或存储．压缩存储．索引存储、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()。100，80，90，60，120，110，130）100，120，110，，80，60，90）100，60，80，90，120，110，130）．(100，80，60，90，120，130，110)、折半查找的平均比较次数为（．n．n/2．log2n．log2(n+1)6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）．必定快．不一定．在大部分情况下要快．取决于表递增还是递减、已知一有向图的邻接表存储结构如下图如示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（．v1，v2，v3，v5，v4．v1，v2，v3，v4，v5．v1，v3，v4，v5，v2．v1，v4，v3，v5，v2、为了方便地对图状结构的数据进行存取操作，则其中数据存储结构宜采用（．顺序存储．链式存储．索引存储．散列存储、在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（．s．s-1．s+1．n10、如图所示，给出由7个顶点组成的无向图。从顶点A出发，对它进行深度优先搜索得到的顶点序列是（．AECDBFG．AGBFDEC．ACEDBGF．ABDGFEC二、填空题1.设0为哈夫曼树的叶子结点数目，则该哈夫曼树共有________个结点。2.有数据WG={7，19，2，6，，3，，10}，则所建Huffman树的树高是________，带权路径长度WPL为________。3.设一棵完全二叉树叶子结点数为k,最后一层结点数，则该二叉树的高度为________________。4.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳。、设G为具有N个顶点的无向连通图，则G中至少有条边。、哈夫曼树（HuffmanTree）又称。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL。7、树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则访问树的；依次先序遍历树的。三、应用题、给定权值集合{1,4,2,6,9,},构造相应的哈夫曼树,并计算它的带权路径长度。、对关键字序列{10，6，，，5，4}，构造一棵平衡二叉（排序）树并画图（要求画出建树过程）。、设有一个有序文件，其中各记录的关键字为（1，，3，4，，6，7，，9，10，11，12，13，14，15当用折半查找算法查找关键字为3，，19时，其比较次数分别为多少？、对有五个结点{A,B,C,D,E}的图的邻接矩阵，01003010060020100500（；（（（作业题（三）一、单项选择题．串的长度是指（）．串中所含不同字母的个数B．串中所含非空格字符的个数．串中所含不同字符的个数D．串中所含字符的个数．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A.BA+141B.BA+180C.BA+222D.BA+225．算法分析的两个主要方面是（．空间复杂性和时间复杂性B．正确性和简明性．可读性和文档性D．数据复杂性和程序复杂性．算法分析的目的是（．找出数据结构的合理性B．研究算法中的输入和输出的关系．分析算法的效率以求改D．分析算法的易懂性和文档性5.下面程序段的时间复杂性的Intfun(intn){inti=1,s=1;While(s<n)S+=++I;ReturnI;}．O(n/2)B．O(lbn)．O(n)D．O()6.线性表是（．一个有限序列，可以为空B．一个有限序列，不能为空．一个无限序列，可以为空D．一个无限序列，不能为空7.带头结点的单链表L为空的判定条件是（．L==NULLB．L-〉next==NULL．L-〉next==LD．L!=NULL8.在一个长度为n的线性表中，x的元素时需要比较元素和移动元素的n+1）/2B．n/2．nD．n+19.一个顺序存储线性表的第一个元素的存储地是90，每个元素的长度是，则第6个元素的存储地址是（．98B．100．102D．10610.如果某链表中最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节时间。．单链表B．双向链表．单循链表D．顺序表二、填空题1.高度为2的二叉树的结点数至有________个，高度为3的二叉树的结点数至有________个。2.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找关键字值20，需做的关键字比较数为________。3.在有n个顶点的无向图中，每个顶点的度最可________。．已知广义表a，b，c，e，f（tail（tail（=。、数组（Array）是（n≥1）个的有序组合，数组中的数据是按顺序存储在一的存储单元中。6.采用顺序存储结构表示三元组表（TripleTable式，称为，简表。7.运算是矩阵运算中最基本的一项，它是将一个mxn的矩阵变成另外一个nxm的矩阵，时使原来矩阵中元素的行和列的位置互换而值保不变。三、应用题、对于下图所示的二叉树，画出二叉链表存储结构图。、请画出下图所示的树所对应的二叉树。ABCDE3.已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。4.已知完全二叉树的第8层有8个结点，则其叶子结点是多少？5.画出如图所示中树的二叉树的表示形式。作业题（四）一、单项选择题1.将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（．nB．2n-1．2nD．n-12.一个有n个顶点的无向连通图，它所包含的连通分量个数为（．0．1．n．n+13.数据文件的基本操作中最重要的操作是（．插入．删除．修改．检索4.对关键码序列，16，32，12，60，2，，72快速排序，从小到大一次划分结果为（．(2,5,12,16)26(60,32,72)．(5,16,2,12)28(60,32,72)．(2,16,12,5)28(60,32,72)．(5,16,2,12)28(32,60,72)5.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，．堆排序．快速排序．插入排序．归并排序．算法分析的目的是（．找出数据结构的合理性B．研究算法中的输入和输出的关系．分析算法的效率以求改进D．分析算法的易懂性和文档性7.二叉树的第I层上最多含有结点数为（）IB．2．2I-1-1C．2I-1D．I-1．循环队列存储在数组A中，长度为，则入队时的操作为（A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)9.广义表满足Head(A)=Tail(A)，则A为（ABCD10.在一棵度为的树中，度为3的结点数为个，度为的结点数为个，度为1的结点数为2个，则度为的结点数为（）个。A．3B．4C．5D．6二、填空题1.在一个循环队列中，队首指针指向队首元素的_________。2.数组中每一个数据通常称为，用下标区分，其中下标的个数由数组的决定。3.一个图的表示法是唯一的，而表示法是不唯一的。4.在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许个，最少允许个5.对关键字序列（52，，63，44，48，）进行一趟快速排序之后的得到结果为。10.高度为1的平衡二叉树的结点数至少有________个，高度为2的平衡二叉树的结点数至少有________个。三判断1.顺序存储结构属于静态结构，链式结构属于动态结构。（）2.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）3.带权无向图的最小生成树必是唯一的。（）4.B-树和B+树都可用于文件的索引结构。（）5.在用堆排序算法排序时，如果要进行增序排序，则需要采用"大根堆"）四、应用题1.模式串p="abaabcac"的next函数值序列为多少？2.设二维数组A[5][6]的每个元素占4个字节，已知LOC（）=1000，A共占多少个字节？A的终端结点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少？3.设a,b,c,d,e五个字符的编码分别为1,2,3,4,5ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（）方法将它们存入具有10个位置的表中。（）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。4.给定一个关键字序列{24，19，32，43，38，，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？作业题（五）一、单项选择题1.一组记录的关键码为（46，79，56，38，，84的一次划分结果为（A．(38,40,46,56,79,84)B．(40,38,46,79,56,84)C40,38,46,56,79,84)D．(40,38,46,84,56,79)2．广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。GetHead(GetTail(GetHead(GetTail(GetTail(A)))))A.(g)B.(d)C.cD.d．对于有n个结点的二叉树,其高度为（）．nlognB．lognC．log2n+1D．不确定4.如图所示，给出由个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是（A．1354267B．1347625C．1534276D．12476535.采用邻接表存储的图，其深度优先遍历类似于二叉树的（A．中序遍历B．先序遍历C．后序遍历D．按层次遍历6.已知有向图G=(V,E)，其中V={V,V,V,V,V,V6,V}，E={<V,V>,<V1,V3>,<V,V4>,<V,V5>,<V3,V>,<V,V>,<V,V6>,<V5,V>,<V6,V>},G的拓扑序列是（A．V1,V,V4,V,V2,V,V7B．V1,V,V2,V,V4,V,V7C．V1,V,V4,V,V2,V,V7D．V1,V,V5,V,V4,V,V77.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（N为线性表中结点数，且每次查找都是成功的。A．N+1B．2logNC．logND．N8.下面关于m阶B树说法正确的是（①每个结点至少有两棵非空子树；②树中每个结点至多有m一个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。A．①②③B．②③C．②③④D．③9.已知一个线性表（，，，63，，48h(k)=k%7计算Hash地址进行散列存储，若利用链地址法处理冲突，则在该Hash表上进行查找的平均查找长度为（A．1.0B．7/6C．4/3D．3/210.在排序算法的实施过程中，使用辅助存储空间为O（1）的有（A．简单排序法B.快速排序法C．归并排序法D.基数排序法二、填空题1.n（n大于1）个结点的各棵树中，其中深度最大的那棵树的深度是，它共有________个叶子结点和________个非叶子结点。2.设一棵后序线索树的高是，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60，x是y的左孩子。则确定x的后继最多需经过________中间结点（不含后继及x本身）3.高度为（第2层为叶子）的3阶B-树中，最多有________个关键字。4.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为无序的表，则平均情况下最省时间的是________算法。5.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。6.串的链式存储结构是将存储区域分成一系列大小相同的结点,每个结点有两个域域和域。其中域用于用于存放数据，域用于存放下一个结点的指针三．判断1.顺序存储的线性表可以随机存取。（）2.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）3.十字链表是无向图的一种存储结构。（）4.折半查找方法适用于排列连续顺序文件的查找。（）5.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）四、应用题1.用十字链表表示一个有k个非零元素的mxn的稀疏矩阵，则其总的结点数为多少？2.G=(V,E)是一个带有权的连通图,则：（1G的最小生成树；（2G为下图所示请找出G的所有最小生成树。3.请分别叙述在一个连续顺序文件中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文件中记录应该满足什么条件？4.设待排序文件之排序码为（88，33，，55，99，11，66对上述文件进行排序，用图示说明排序过程。作业题一参考答案：一、单项选择题、C2、B3、D4、C5、B、B7、A8、C9、D10、D二、填空题、非零元很少（或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊）(或后进后出)、简单选择排序、O(n2)，O(e)，O(n)、邻阵矩阵，邻接表三、算法答：intcount=0;voidonechild(Btreet){if(t!=NULL){onechild(t->lchild);onechild(t->rchild);if(t->lchild!=NULL&&(t->rchild!=NULL||t->lchild!=NULL&&t->rchild==NULL)count++;}}四、应用题、答：、答：（）（）CC112GGF（）（）A3A3DDCC1142GF2GF（）（6）AA33DDBBEC6C15415422GFGF、答：由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。用线性探测再散列解决冲突，ASLsucc=27/10、答：成功查找平均比较查找长度为：（n+1）/n[log2（n+1）]-1。作业题二参考答案：一、单项选择题、C2、C3、B4、C5、D、C7、C8、B9、A10、C二、填空题、2n-1、6，261、logk+1、25、N-1、最优二叉树，最小的二叉树、根结点，各子树三、应用题、答：不唯一，型对即可2291367此树的带权路径长度WPL=9*1+6*2+4*3+(1+2)*4=45、答：（）插入10(2)插入6(3)插入3(4)6101010调整31066（）插入2（6）插入5（）插入4（）665631031036310调整222410255、答：当关键字为时，比较次数为4；当关键字为8时，比较次数为1；当关键字为19时，查找不成功；、答：（2）略（）深度优先遍历序列：ABCDE广度优先遍历序列：ABCED（4）关键路径A--B（长100）作业题三参考答案：一、项、D2、B3、A4、C5、D、A7、B8、C9、B10、D二、填空题、2，3、4、n-1、e、相同类型数据，地6.三元组顺序表，三元组7.矩阵置三、应题、答：①二叉链表②∧③∧④∧⑤∧⑥∧⑦⑧∧∧∧(2∧⑨∧、答：ABCDE3.答：Prim算法构造最小生成树的步如24题所示，为节省篇幅，这里用Kruskal算法，构造最小生成树过程如下：（下图也可(2,4)代替(3,4),(5,6)代替(1,5)）即：4.答：由完全二叉树的定义可知，除最后一层外，其他各层的结点是满的。d层，除最后一层外各层的结点个数，，，8，16，，⋯，即第i层的结点个数为2i-1。这里第8层有个结点，显第8/层是最后的一层，那第层的结点个数为27-1=64个，其中的4个结点8个叶子结点，余下的为叶子结点，个数为64-4=60，所以该完全二叉树的叶子结点个数为个。5.答：对应的二叉树形式如图所示：作业题四参考答案：一、单项选择题1.A2.B3.D4.B5.D、C7、C8、C9、B10、D二、填空题1.答：前一个位置2.答：数组元素，数组元素，维数3.答：邻阵矩阵，邻接表4.答：，45.答：[4844]52[648091]、1，2三．判断1.答：√2.答：×3.答：×4.答：√5.答：√四、应用题1.答：模式p的next函数值如下：2.答：A共120个字节。4的起始地址为：1116。按行优先存储时，5的起始地址