2022年南京农业大学信息科学技术学院853计算机专业基础综合之数(2)

24．栈和队列都是限制存取点的线性结构。（ ）

【答案】

25．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）

【答案】×

【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。

26．数据结构的抽象操作的定义与具体实现有关。（ ）

【答案】

【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表示和实现无关。

27．一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第的最多结点数为

【答案】√

【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为 层具有最大的结点数为

28．堆是满二叉树。（ ）

【答案】× 【解析】堆的定义： n个关键字序列

且

且

称为堆，当且仅当该序列满足如下性质（简称为堆性质）：

层全满时，

此时从根结点到第

余下的

个结点在第k层的任一位置上。（ ）

层具有

小根堆：满足第①种情况的堆； 大根堆：满足第②种情况的堆。 因此并不能保证堆是满二叉树。

四、算法设计题

29．设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中（注：按层从上到下，由左到右）。

【答案】算法如下：

typedef struc {DiTree data; int num;}tnode // num是结点在一维数组中的编号tnodc Q[maxsize]; //队列，容量足够大

void BiToSeqt{BiTree t,ELemType seq[]}

//本算法将二叉树的二叉链表存储结构转换为顺序存储结构seq {int front=0, rear:=0; tnode q; Bitree p; if（!t） exit（0）;

for（i=1;i<maxsize;i++ ） seq[i]=‘#’;//初始化，#代表虚结点 tq.data=t;tq.num=l; Q[++rear]=tq;//根结点入队 while（front<rear）

{tq=Q[++front];p=tq.data;l=tq.num;seq[i]=p->data; //存入顺序存储结构 if（p->lchild）{tq.data=p->lchild;tq.num=2*i;Q[++rear}//左子女入队 if（p->rchild）{tq.data=p->rchild;tq.num=2*i+1;Q[++rear]=tq;}//右子女入队 } }

30．已知字符串

中存放一段英文，写出算法

其多余的字符送

31．设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

【答案】（1）递归算法如下：

（2）非递归算法如下：

将其按给定的长度n格式化

成两端对齐的字符串

【答案】算法如下：

32．已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。

【答案】算法如下：

33．设A和B均为下三角矩阵，每一个都有n行n列。因此在下三角区域中各有无素。另设有一个二维数组C，它有n行

个

列。试设计一个方案，将两个矩阵A和B中的下三

和B的矩

角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素阵元素在C中的存放位置下标的公式。

【答案】算法如下：

34．设记录

的关键字为

树结点

的败者树，要求除

指向败者记录，

和

为全胜记以外，只用

录下标。写一算法产生对应上述

辅助空间。 【答案】算法如下：

35．已知二叉树T，试写出复制该二叉树的算法（t→T）。

【答案】算法如下：

BiTree Copy（BiTree t）//复制二叉树t的非递归算法

/ /Q是二叉树的结点指针的队列，容量足够大

else

}//结束本题

36．设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？

【答案】算法如下：

构造的哈希表如图所示：

图 构造的哈希表

查找成功时的平均查找长度

五、应用题

37．线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么？

【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。

（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O（1）。

38．给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

（1）归并排序，每归并一次书写一个次序。 （2）快速排序，每划分一次书写一个次序。

（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 【答案】（1）2—路归并第一趟：18，29，25，47，12，58，10，51: 第二趟：18，25，29， 47，10，12，51，58;

第三趟：10，12，18，25，29，47，51，58

（2）快速排序第一趟：10，18，25，12，29，58，51，47; 第二趟：10，18，25，12，29，47，51，88; 第三趟：10，12，18，25，29，47，51，88 （3）堆排序

建大堆：58，47，51，29，18，12，25，10; ①51，47，25，29，18，12，10，58; ②47，29，25，10，18，12，51，58; ③29，18，25，10，12，47，51，58; ④25，18，12，10，29，47，51，58; ⑤18，10，12，25，29， 47，51，58; ⑥12，10，18，25，29，47，51，58; ⑦10，12，18，25，29， 47，51，58

39．将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴.顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：

图2

40．如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。

41．设输入序列为2,3,4,5,6,利用一个栈能得到序列2,5,3,4,6吗?栈可以用单链表实现吗？

【答案】不能得到序列2,5,3,4,6。因为根据输入序列，2进栈之后，2出找，3,4,5依次进栈。5出栈，此时栈中剩下3,4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。

42．带权 …… 此处隐藏：2442字，全部文档内容请下载后查看。喜欢就下载吧 ……