【数据结构】一起来刷笔试题--05
点击题目下空白处可查看答案
一、
n个结点的线索二叉树上含有的线索数？
线索二叉树中每个节点有两个指针域。
二叉树中（除了根节点外）每个节点都有父结点，其与父结点的连线即为一条边。若二叉树有 n 个节点，则有 n-1 条边，所以这 n-1个 条边占掉了 n-1 个指针域。故剩下的 2n-(n-1)=n+1 个指针域（包括空指针）就是线索数。
二、
有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，求所需的字节数。
将非零元素所在行、列、非零元素的值构成一个三元组（i，j，v） 。
对于该题：
每个非零元素占 3*2=6 个字节，共 10 个非零元素，需 6*10 = 60 个字节；
此外，还一般要用三个整数来存储矩阵的行数、列数和总元素个数，又需要 3*2 = 6 个字节；
总共：60 + 6 = 66 个字节。
三、
广义表 (((a,b,c),d,e,f)) 的长度？
广义表即我们通常所说的列表（lists)。它放松了对表元素的原子性限制，允许他们有自身结构。
广义表的长度：去掉一层括号剩下的是几部分
广义表的深度：总共含括号的层数
在本题中：
广义表去掉一层括号后为 （（a,b,c）,d,e,f），所以长度为 1；总共能去掉 3 层括号，所以深度为 3 。
四、
深度为 k 具有 n 个结点的完全二叉树，求其编号最小的叶结点序号。
最小叶节点可能在最后一层，也可能在倒数第二层，因此 2^(k-2) 并不一定是最小叶节点的序号。因而我们需要从 n 个结点入手。
完全二叉树中，根节点的序号为 i，那么根节点的左节点序号是 2*i，右节点的序号是 2*i+1，已知最后一个节点的序号是 n，因此它的父节点序号是 [n/2]，编号最小的叶节点位于该父结点的右边，因此序号为 [n/2]+1 。
往期文章：