数据结构习题及答案(4)

subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：

Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF

解：con(x,y)返回x和y串的连接串，即 con(x,y)＝‘ABCDEFGPQRST’； subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，则

subs(s1, 2, len(s2))＝subs(s1, 2, 5)=? BCDEF?; subs(s1, len(s2), 2)＝subs(s1, 5, 2)=? EF?; 所以con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))＝con(? BCDEF?, ? EF?)之连接，即BCDEFEF （ A ）4. 〖01年计算机系考研题〗假设有60行70列的二维数组a[1?60, 1?70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。（无第0行第0列元素）

Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不对

答：此题与填空题第8小题相似。（57列×60行＋31行）×2字节＋10000=16902

( B )5. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是：

解：注意B的下标要求从1开始。 先用第一个元素去套用，可能有B和C； 再用第二个元素去套用B和C，B=2而C＝3（不符）； 所以选B ?a1,1?a2,1?A??????an,1a2,2an,2??????an,n??Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j

6. 【91初程P78】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。 存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是 B 和 C 。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是 D 和 E 。 供选择的答案：

A～E：①28 ② 44 ③ 76 ④ 92 ⑤ 108

⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188 答案：ABCDE=8, 3, 5, 1, 6

7.【94程P12】 有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 A 个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A[2,4]的第一个字节的地址是 C 。若按列存储，则A[5,7]的第一个字节的地址是 D 。 供选择的答案

A～D：①12 ② 66 ③ 72 ④ 96 ⑤ 114 ⑥ 120

⑦ 156 ⑧ 234 ⑨ 276 ⑩ 282 （11）283 （12）288 答案：ABCD=12, 10, 3, 9 三、简答题（每小题5分，共15分）

1. 【其他教材】已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？

解：公式教材已给出，此处虽是方阵，但行列公式仍不相同； 按行存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K 按列存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K

2.【全国专升本资格考试】递归算法比非递归算法花费更多的时间，对吗？为什么？ 答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。

四、计算题（每题5分，共20分）

1. 【严题集4.3①】设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’,

求Replace(s,’STUDENT’,q) 和Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。

2. 用三元组表表示下列稀疏矩阵：

?00000000??00000000??0000?02????000090??03000800??????000000?00000000?? (2)?(1)?

?00060000?005000?????000000??00000000????00000005?000030?????20000000?

3. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。

?646??455??122??111??????2112??249???(1)?313? (2)??

?328??444??356??????536?437????6116??

五、算法设计题（每题10分，共30分）

1. 【严题集4.12③】 编写一个实现串的置换操作Replace(&S, T, V)的算法。

2. 【严题集5.18⑤】试设计一个算法，将数组An 中的元素A[0]至A[n-1]循环右移k位，并要求只用一

个元素大小的附加存储，元素移动或交换次数为O(n)

附加题： 利用C的库函数strlen, strcpy（或strncpy）写一个算法void StrDelete(char *S,int t,int m) ，删除串S中从位置i开始的连续的m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均被删去。

提示：strlen是求串长(length)函数：int strlen(char s); //求串的长度

strcpy是串复制(copy)函数：char *strcpy(char to,char from); //该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。

第6章 树和二叉树

一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）

（ √ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（ × ）2.二叉树中每个结点的两棵子树的高度差等于1。

（ √ ）3.二叉树中每个结点的两棵子树是有序的。 （ × ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（ × ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键

字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点）

（ × ）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （ × ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（ × ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）

（ √ ）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中

有n+1个为空指针。

（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。

（ √ ）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 二、填空（每空1分，共15分）

1． 由３个结点所构成的二叉树有 5 种形态。

2. 【计算机研2000】 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3． 一棵具有２５７个结点的完全二叉树，它的深度为 9 。 （ 注：用? log2(n) ?+1= ? 8.xx ?+1=9

4.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有 350 个叶子结点。

答：最快方法：用叶子数＝[n/2]＝350

5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，

所以非空右子树数＝0.

6. 【严题集6.7③】 一棵含有n个结点的k叉树，可能达到的最大深度为 n ，最小深度为 2 。

答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。)

7. 【96程试题1】 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 L R N 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B 。

解：法1：先由已知条件画图，再后序遍历得到结果；

法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前序先确定root，由中序先确定左子树。例如，前序遍

历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定在最后面。

法3：递归计算。如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同样处理，则问题得解。 8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度 为 O(n) 。

答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1，包括叶子的空域也递归了一次。

9. 【计算机研2001】 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 33 。

解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33 (15)

(9) (6) （注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）

4 5 3 (3) （注：合并值应排在叶子值之后）

1 2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题及答案(4)在线全文阅读。