《数据结构真题》由会员分享，可在线阅读，更多相关《数据结构真题（10页珍藏版）》请在金锄头文库上搜索。
1、全真模拟试题（二）一、单项选择题（在每个小题的4个备选答案中，选出正确的答案，并将其号码填在 题后的括号内。每小题2分，共24分）1一个具有n个顶点的无向完全图的边数为（） n（n+1）/2 n（n-1）/2 n（n-1） n（n+1）2在索引顺序表中查找一个元素，可用的且最快的方法是（ ） 用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 用二分查找法确定元素所在块，再用二分查找法在相应块中查找 3若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元
2、素，则采用（ ）存储方式最节省运算时间。 单链表 双链表带头结点的双循环链表 容量足够大的顺序表 4串是（ ）一些符号构成的序列有限个字母构成的序列一个以上的字符构成的序列 有限个字符构成的序列 5堆排序在最坏情况下，其时间复杂性为（ ） O（nlogn） 0（n2） Odogz） OQogQn）6. 快速排序的记录移动次数（）比较次数，其总执行时间为0 （nlog2n）。 大于 大于等于 小于等于 小于7. 棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号，（号码为1-n）,编 号须具有如下性质：二叉树中任一结点V,其编号等于其左子树中结点的最大编号加1。而 其右子树中结点的最小编号等于
3、V的编号加1。试问应按（）遍历顺序编号。 前根 中根后根层次8.3个结点可构成（ ）个不同形态的二叉树。 2 3 459对有n个记录的有序表采用二分查找，其平均查找长度的量级为（）0（10&2口） OSlogQn） 0（n） 0（n2）10. 对有n个记2录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查找 长度的量级为（ ）0（n） 0（nlog2n） 0（1）（logR11. 栈操作的原则是（ ） 先进先出 后进先出 栈顶插入 栈顶删除12. 设矩阵A是一对称矩阵（a =a ,1=i,j=8），若每个矩阵元素占3个单元，将其上三ij ji角部分（包括对角线）按行序为主序存放在数组
4、B中，B的首地址为1000，则矩阵元素a67 的地址为（ ）1031109310961032二、判断题（判断下列各题是否正确，正确在括号内打“M”，错的打“X”。每小 题1分，共10分）1如果两个串含有相同的字符，则这两个串相等。 （ ）2数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。 （ ）3在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表 中元素个数有关，而且与每一块中元素个数有关。（ ）4在顺序表中取出第i个元素所花费的时间与i成正比。（）5在栈满情况下不能作进栈运算，否则产生“上溢”。（ ）6二路归并排序的核心操作是将两上有序序列归并为一个有序
5、序列。 （）7对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可 访问图的每个顶点.（ ）8二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树：若它的左子树 非空，则根结点的值大于其左孩子的值;若它的右子树非空，则根结点的值小于其右孩子 的值。（ ）9在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动， 则该算法是不稳定的。（ ）10一个有向图的邻接表和逆邻接表中表结点的个数一定相等。 （）三、填空题（每空2分，共26分）1. 在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句： ； L-next=U-next； free（U）；2
6、有一个长度为20的有序表采用二分查找方法进行查找，共有个元素的查找长度为3。3. 采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递 增，则排序过程中记录的比较次数为。若A的初始状态为递减排列，则记录的交换次数为。4在无头结点的双链表中，指针P所指结点是第一个结点的条件是。5. G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是图。6. 如果一个有向图中没有，则该图的全部顶点可能排成一个拓扑序列。7. 深度为8 （根的层次号为1）的满二叉树有个叶子结点。8将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X,其双亲PARE
7、NT （X）的编号为。9. 设某闭散列表HT未满，散列函数H （KEY）为键值第一字母在字母表中的序号，处 理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的 顺序输出闭散列表中所有键值的算法。void printword（keytype HTm） for（i=1;i=26;i+） j=i;while() if () printf(“datatype”,HTj)j=(j+1)% m;10.设有一个链队，结点结构为data|next, front为队头指针，rear为队尾指针, 当执行入队操作时需执行下列语句：malloc(p)； pdata二x; pnext=NUL
8、L；四、应用题（共26分）1有向图G的邻接表如下图所示，若删去图G中的边VV3, V6和VV4, V5，试 画出修改后图的邻接表。（4分）顶点入度23.；A.63.31A5A2. 有向图如下图所示，写出以V1为出发点对图进行深度优先搜索所得到的所有可能 的访问序列。（4分）3. 对于键值序列（49,38,65,97,76,13,27,50）,使用堆排序算法完成排序过程。要 求：画出初始堆（用二叉树表示）。画出分别输出13,27后重建的两个堆。（5分）4. 一个深度为d （根的层次号为1）的满K叉树有如下性质：第d层上的结点都是叶子 结点，其余各层上的每个结点都有K棵非空子树。如果从根这一层开始
9、从左到右顺序逐层 对全部结点编号，且根结点的编号为1,问编号为n的结点有右兄弟的条件是什么？其右 兄弟的编号是多少？ （3分）5给定权值5,10,12,15,30,40,构造相应的哈夫曼树，要求写构造歩骤。（4分）6.已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec），按表中顺 序依次插入初始为空的二叉排序树，要求：画出建立的二叉排序树。（4分）求出在等概率情况下查找成功的平均查找长度。（2分）五、设计题（共14分）1设有一单链表L,结点结构为data|next,结点个数至少3个，试画出链表L的结 构图，并编写算法判断该单链表 L中的元
10、素是否成等差关系，即：设各元素值次为a,a,a,.,a，判断 a -a =a -a 是否成立，其中 i 满足 2二i二n-l.(8 分)123 ni+1 i i i-12. 设有一棵二叉树以二叉链表作为存储结构，结点结构为lchild|data|rchild，其中 data域中存放一个字符，设计一个算法按前根遍历顺序仅打印出data域为数字的字符(即 0二data=9) (6分)全真模拟试题(一)一、单项选择题(在每小题的4个备选答案中，选出正确的答案，并将其号码填在题干的括号内。每小题2分，共24分)1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用)存储方式最节省时
11、间。单链表 双链表单向循环顺序表)符号构成的集合字符构成的集合2. 串是任意有限个(符号构成的序列字符构成的序列3. 设矩阵A (a ,lWi,jW 10)的元素满足：ija.M0(i三j, lWi, jW 10)ijaij=0 (ij, lWi, jW 10)ij现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元 素占有4个单元，则元素A95 的首址为23402336216421604. 如果以链表作为栈的存储结构，则退栈操作时() 必须判别栈是否满 对栈不作任何判别 必须判别栈是否空 判别栈元素的类型5. 设数组Data0.m作为循环队列SQ的存储空间，front为
12、队头指针，rear为队 尾指针，则执行出队操作的语句为( )front二front+1front=(front+1)% mrear=(rear+1)%mfront=(front+1)%(m+1)6. 深度为6(根的层次为1)的二叉树至多有()结点。 643231637. 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点 X 的双亲编号为( )242523无法确定8. 设有一个无向图G= (V，E)和G = (V，E)如果G为G的生成树，则 下面不正确的说法是( )G为G的子图G为G的边通分量G为G的极小连通子图且V =V G为G的一个
13、无环子图9. 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值( ) 一定都是同义词 一定都不是同义词 都相同不一定都是同义词10. 二分查找要求被查找的表是( ) 键值有序的链接表 链接表但键值不一定有序 键值有序的顺序表 顺序表但键值不一定有序11当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为( ) n2 n log2n 1 og2n n-112.堆是一个键值序列匕也,，kJ,对i=l,2,.,|_n/2_|,满足()kWk2Wkk k ki 2i 2i+1i 2i+1 2ik Wk 且 k Wk (2i+lWn) k Wk 或 k Wk (2i+
14、lWn)i 2i i 2i+1i 2i i 2i+1二、判断题(判断下列各题是否正确，正确在括号内打“V”，错的找“X”。每 小题1分，共10分)1. 双链表中至多只有一个结点的后继指针为空。()2. 在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。()3. 对链表进行插入和删除操作时，不必移动结点。()4. 栈可以作为实现程序设计语言过程调用时的一种数据结构。()5. 在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧va,b。 ( )i6. 对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。()7. “顺序查找法”是指在顺序表上进行查找的方法。()8. 向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。()9. 键值序列A，C，D，E，F，E，F是一个堆。10. 二路归并时，被归并的两个子序列中的关键字个数一定要相等。()三、填空题(每空2分，
