数据结构试卷B卷

《数据结构试卷B卷》由会员分享，可在线阅读，更多相关《数据结构试卷B卷（10页珍藏版）》请在金锄头文库上搜索。

1、数据结构试卷 B一、填空题（每空 1 分，共 15 分）1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能 插入和删除元素。2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。5在具有n个单元的循环队列中，队满时共有个元素。6.假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查 找成功的结点数为 ；比较四次查找

2、成功的结点数为 ；平均查找长度为。二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题 1 分，共10 分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（）8. 两个栈共享一片连续内

3、存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构()10.个栈的输入序列是12345，则栈的输出序列不可能是12345。三、单项选择题(每小题1分，共20分)()1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为:(A)存储结构(B)逻辑结构(C)顺序存储结构(D)链式存储结构()2.若已知一个栈的入栈序列是1, 2,3,，n,其输出序列为p1, p2, p3,，pn,若 p1=n,则 pi 为A.i B. n二iC. n-i + 1D.不确定()3.判定一

4、个栈ST (最多元素为m0)为空的条件是A. ST-top0 B. ST-top=0C. ST-topm0D. ST-top二m0()4设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分(如下图所示)按行 序存放在一维数组B 1, n(n-l)/2中，对下三角部分中任一元素a/iWj),在一维数组B中下标 k的值是：A. i(i-1)/2+j-1B.i(i-1)/2+jC. i(i + 1)/2+j-1D. i(i + 1)/2+ja1,1aaA =2,12,2Aaa1- n ,1n ,2Aan ,n()5 具有n(n0)个结点的完全二叉树的深度为(A) log2 (n)(B)log2( n

5、)(C)logl2(n)+1(D) log2(n)+1()6.有8个结点的无向连通图最少有条边。A . 5B. 6C.7D. 87.数据结构反映了数据兀素之间的结构关系。链表是一种AJ它对于数据元素的插入和删除 B 。通常杳找线性表数据兀素的方法有 C和D两种方法，其中C是一种只适合于顺序存储结构彳一E一的方法；而 D曰-是-种对顺序和链式存储结构均适用的方法。供选择的答案：A:顺序存储线性表 非顺序存储非线性表 顺序存储非线性表 非顺序存储线 性表B:不需要移动结点，不需改变结点指针不需要移动结点，只需改变结点指针只需移动结点，不需改变结点指针既需移动结点，又需改变结点指针C :顺序查找 循

6、环查找条件查找二分法查找D :顺序查找 随机查找二分法查找分块查找E :效率较低的线性查找效率较低的非线性查找效率较高的非线性查找 效率较 高的线性查找答案：A二 B二 C二 D二 E二8. 散列法存储的基本思想是根据一A一来决定B，碰撞(冲突)指的是C，处理 碰撞的两类主要方法是D 。供选择的答案A，C:同B： 存储地址 元素的符号 非码属性 平均检索长度两个元素具有相同序号 元素个数 关键码值 负载因子 散列表空间 两个元素的关键码值不同，而非码属性相 负载因子过大 数据元素过多 建溢出区法和不建溢出区法 拉链法和开地址法C二 D 不同关键码值对应到相同的存储地址 D： 线性探查法和双散列

7、函数法 除余法和折叠法答案：A二 9. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点 的值。并小于等于其右子树上的一切结点的值。现欲把丫10放入此树现把9个数1, 2,3,，8 9填入下图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是，n2的值是 B ，n9的值是_C6n9下面n2与n4之间并使该树保持前述性质，增加的一个结点可以放在_D 供选择的答案AC：1234789DE：n7下面 n8下面n6下面 n1与n2之间n6与n9之间n3与n6之间答案：A二B 二C 二D二 E二四、简答题（每小题 5 分,共 25 分）1. 说明线性表、栈与队的

8、异同点。2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列3. 假设正读和反读都相同的字符序列为回文”，例如， abba和abcba是回文，abcde和 ababab则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正 确输出其回文的可能性？4. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？5. 给定二叉树的两种遍历序列,分别是：前序遍历序列：D, A, C, E, B, H, F,G,I；中序遍历序列：D, C, B, E, H, A, G, I, F,试画出二叉树B,并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉

9、树B的思想 方法。五、阅读理解(每小题5分,共20分)1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在P 结点后插入S结点的核心语句序列。2、阅读下列算法,若有错,改正之。BiTree InSucc(BiTree q)已知q是指向中序线索二叉树上某个结点的指针, 本函数返回指向*q的后继的指针。r=q-rchild;if(!r-rtag)while(!r-rtag)r=r-rchild;return r;/ISucc1. 写出下列程序段的输出结果(队列中的元素类型QEIem Type为char)。 void main( )Queue Q; Init Queue

10、(Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q,y);DeQueue (Q,x); EnQueue (Q,x);DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);2. 简述以下算法的功能(栈和队列的元素类型均为in t)。void algo3(Queue &Q)Stack S; int d; InitStack(S);while(!QueueEmpty(Q)DeQueue (Q,d); Push(S,d

11、);while(!StackEmpty(S)Pop(S,d); EnQueue (Q,d);六、算法设计（每小题 5 分，共 15 分。至少要写出思路）1. 写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。2. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个 数（其中指针P指向该链表的第一个结点）。3. 试写一个算法，判别读入的一个以为结束符的字符序列是否是“回文”。答案一、填空题（每空 1 分，共 15 分）1向量、栈和队列都是_线性_结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶 插入和删除元素；对于队列只能在队尾 插入和 队首

12、删除元 素2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底 。3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的关系和运算等的学科。4. 在顺序表中插入或删除一个元素,需要平均移动表中一半元素，具体移动的元素个数与表 长和该元素在表中的位置有关。5在具有n个单元的循环队列中，队满时共有_口 个元素。8.假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 丄一；比较四次查找成功的结点数为_8；平均查找长度为解：显然，平均查找长度二O （log2n） 5次（25）。但具体是多少次，则

13、不应当按照公式ASL = n1 log2（n +1）来计算（即（21x|og221）/20 = 4.6次并不正确。因为这是在假设n = 2m-l的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为=（1 + 2x2 + 4x3 + 8x4 + 5x5）=74； ASL = 74/20=3.7!二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10 分）X ） 1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类 型。错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。（ X ）2. 在表结构中最常用的是线性表，栈和队列不太常

14、用。错，不一定吧？调用子程序或函数常用，CPU中也用队列。V ） 3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先 出型结构。（ V ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（ X ） 5.线性表的逻辑顺序与存储顺序总是一致的x ) 6.栈和队列是一种非线性数据结构。错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。V )7.栈和队列的存储方式既可是顺序方式，也可是链接方式。V ) 8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。x )9.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。(x )10.个栈的输入序列是12345，则栈的输出序列不可能是12345。错，有可能。三、单项选择题(每小题1分