数据结构试卷B卷(含答案)(9页).doc

《数据结构试卷B卷(含答案)(9页).doc》由会员分享，可在线阅读，更多相关《数据结构试卷B卷(含答案)(9页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、，p3，pn，若p1=n，则pi为 i n=i n-i+1 不确定（ ）3. 判定一个栈ST（最多元素为m0）为空的条件是ST-top0 ST-top=0 ST-topm0 ST-top=m0（ ）4设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B 1, n(n-1)/2 中，对下三角部分中任一元素ai,j(ij), 在一维数组B中下标k的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j（ ）5具有n(n0)个结点的完全二叉树的深度为 。() log2(n) () log2(n) () log2(n)

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

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

7、法和折叠法 拉链法和开地址法答案：A B C D 9. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。现把9个数1，2，3，8，9填入下图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把放入此树并使该树保持前述性质，增加的一个结点可以放在 D 或 E 。供选择的答案AC： 1 2 3 4 5 6 7 8 9DE： n7下面 n8下面 n9下面 n6下面 n1与n2之间 n2与n4之间 n6与n9之间 n3与n6之间 答案：A B C D E 四、简答题（每小

8、题5分，共25分）1. 说明线性表、栈与队的异同点。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. 写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。void main( )Queue Q; Init Q

10、ueue (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. 简述以下算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Pus

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

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

13、度O（log2n）top0 ST-top=0 ST-topm0 ST-top=m0( B )4、 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B 1, n(n-1)/2 中，对下三角部分中任一元素ai,j(ij), 在一维数组B中下标k的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j（ C ）5具有n(n0)个结点的完全二叉树的深度为 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+1（ C ）6. 有8个结点的无向连通图最少有 条边。 A5 B. 6

14、 C. 7 D. 8 7、 答案：A B C D E 8、 答案：A B C D 9、答案：A B C D E 四、简答题（每小题4分，共20分）1.说明线性表、栈与队的异同点。刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。2. 试

15、写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A3.假设正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde 和ababab则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？答：线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现。哪种

16、方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是）若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。4.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（1？），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部

17、分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（next=P-next;(1) P-next=S;(11) P=L;(8) while(P-next!=Q)P=P-next;(10) P=Q;(4) S-next=P-next;P-next=S;2、答：这是找结点后继的程序。共有3处错误。注：当rtag1时说明内装后继指针，可直接返回，第一句无错。当rtag0时说明内装右孩子指针，但孩子未必是后继，需要计算。中序遍历应当先左再根再右，所以应当找左子树直到叶子处。r=r-lchild; 直到LTag=1； 应改为：while(!r-Ltag)r=r-Lchil

18、d;BiTree InSucc(BiTree q)/已知q是指向中序线索二叉树上某个结点的指针，/本函数返回指向*q的后继的指针。r=q-rchild; /应改为r=q；if(!r-rtag) while(!r-rtag)r=r-rchild; /应改为 while(!r-Ltag) r=r-Lchild;return r; /应改为return r-rchild；/ISucc3. 写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQu

19、eue (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);答：输出为“char”。4. 简述以下算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) P

20、op(S,d); EnQueue (Q,d); 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。invsl(n,a)int n;ET a;int k;ET t;for (k=1; k=n/2; k+)t=ak-1; ak-1=an-k; an-k=t;return;六、算法设计（每小题5分，共15分。至少要写出思路）1、输入：长度为n的线性表数组A(1:n)输出：逆转后的长度为n的线性表数组A(1:n)。C语言描述如下（其中ET为数据元素的类型）：2. 假设一个数组squm存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针

21、值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。解：这就是解决队满队空的三种办法之 设置一个布尔变量以区别队满还是队空（其他两种见简答题）；思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1；若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。3.试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。答：编程如下：int Palindrome_Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c); /同时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test