《数据结构考试问答题》由会员分享，可在线阅读，更多相关《数据结构考试问答题（11页珍藏版）》请在金锄头文库上搜索。
1、1我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程序？我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程序？答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言）答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言） 。2.【严题集严题集 1.2】数据结构和数据类型两个概念之间有区别吗？数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而
2、且还在其上定义了一组操作。的数据元素，而且还在其上定义了一组操作。3. 简述线性结构与非线性结构的不同点。简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。一对一的，非线性结构反映结点间的逻辑关系是多对多的。1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一） ；要求内存中可用存储单元的地；要求内存中可用存储单元的地址必须是连续的。址必须是连
3、续的。优点：存储密度大（优点：存储密度大（1？）？） ，存储空间利用率高。缺点：插入或删除元素时不方便。，存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（data);traversal(root-lchild);printf(“%c”, root-data); t
4、raversal(root-rchild); 4.给定如图所示二叉树给定如图所示二叉树 T，请画出与其对应的中序线索二叉树。，请画出与其对应的中序线索二叉树。 解：要遵循中序遍历的轨迹来画出每个前驱和后继。解：要遵循中序遍历的轨迹来画出每个前驱和后继。 中序遍历序列：中序遍历序列：55 40 25 60 28 08 33 5428 253340 60 08 5455五、阅读分析题（）五、阅读分析题（） 1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：A B D F J G K C E H I L
5、 M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A2. （P60 4-27）把如图所示的树转化成二叉树。把如图所示的树转化成二叉树。 答：注意全部兄弟之间都要连线答：注意全部兄弟之间都要连线 （包括度为（包括度为 2 的兄弟）的兄弟）,并注意原有并注意原有 连线结点一律归入左子树，新添连连线结点一律归入左子树，新添连 线结点一律归入右子树。线结点一律归入右子树。ABE CK F H DL G IM J3.阅读下列算法，若有错，改正之。28 25 33 40 60 08 54 55BiTree InSucc(BiTree
6、 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； /ISucc答：这是找结点后继的程序。 共有 3 处错误。 注：当 rtag1 时说明内装后继指针，可 直接返回，第一句无错。 当 rtag0 时说明内装右孩子指针，但孩 子未必是后继，需要计算。中序遍历应当 先左再根再右，所以应当找左子树直到叶 子处。
7、r=r-lchild; 直到直到 LTag=1； ； 应改为：while(!r-Ltag)r=r-Lchild;N I LN I L4.画出和下列二叉树相应的森林。 答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。1.已知如图所示的有向图，请给出该图的已知如图所示的有向图，请给出该图的: （1）每个顶点的入每个顶点的入/出度；出度； （2）邻接矩阵；邻接矩阵； （3）邻接表；邻接表； （4）逆邻接表。逆邻接表。答案：答案：顶点123456入度出度2.请对下图的无向带权图：请对下图的无向带权图： （1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；写出它的邻接矩阵，并按普里姆算法求
8、其最小生成树； （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。解：设起点为解：设起点为 a。可以直接由原始图画出最小生成树，而且最小生。可以直接由原始图画出最小生成树，而且最小生 成树只有一种（类）成树只有一种（类）! 邻接矩阵为：邻接矩阵为： PRIM 算法（横向变化）：算法（横向变化）： VbcdefghUV-UVexlowcosta 4a 3aaaaaab,c,d,e,f,g,hVexlowcosta 40c 5aaac 5a,cb, d,e,f,g,hVexlowcost00c 5b 9aac 5a,c,bd,e,f,g,hV
9、exlowcost000d 7d 6d 5d 4a,c,b,d e,f,g,hVexlowcost000d 7d 6d 50a,c,b,d ,h e,f,g Vexlowcost000d 7g 200a,c,b,d ,h ,g f,e Vexlowcost000f 3000a,c,b,d ,h ,g, f e Vexlowcost0000000a,c,b,d ,h ,g, f, e 邻接表为：邻接表为：ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3064560252036307945670555505395504340最小生成树最小生成树 fd6e3g2
10、gd5f2h6hc5d4g6先罗列：先罗列：f-2-g a3-c f3e a4-b d4h (a,b,c) (e,f,g) (d,h) 取取 b5d, g5-d 就把三个连通分量连接起来了。就把三个连通分量连接起来了。3.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点 1 出发进行遍历所得出发进行遍历所得 的深度优先生成树和广度优先生成树。的深度优先生成树和广度优先生成树。4.试利用试利用 Dijkstra 算法求图中从顶点算法求图中从顶点 a 到其他各顶点间的最短路径，到其他各顶点间的最短路径， 写出执行算法过程中各步的状
11、态。写出执行算法过程中各步的状态。解：最短路径为：（解：最短路径为：（a,c,f,e,d,g,b）克鲁斯卡尔算法步骤克鲁斯卡尔算法步骤 (按边归并按边归并,堆排序堆排序)：1.1.对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？性查找的速度快，这种说法对吗？答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例
12、如所查数据位于首位时，则线性查找快；而二分查找则慢得多。2.假定对有序表：（假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试）进行折半查找，试 回答下列问题：回答下列问题： （1）画出描述折半查找过程的判定树；画出描述折半查找过程的判定树； （2）若查找元素若查找元素 54，需依次与哪些元素比较？，需依次与哪些元素比较？ （3）若查找元素若查找元素 90，需依次与哪些元素比较？，需依次与哪些元素比较？ （4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解：解：（1 1）先画出判
13、定树如下（注：先画出判定树如下（注：mid=mid= (1+12)/2(1+12)/2 =6=6）：）：30 5 633 3 7 7 4242 87874 4 2424 5454 7272 9595(2) 查找元素查找元素 54，需依次与，需依次与 30, 63, 42, 54 等元素比较；等元素比较； (3) 查找元素查找元素 90，需依次与，需依次与 30, 63,87, 95, 72 等元素比较；等元素比较； （4） 求求 ASL 之前，需要统计每个元素的查找次数。判定树的前之前，需要统计每个元素的查找次数。判定树的前 3 层共查找层共查找 12243=17 次；次； 但最后一层未满，不
14、能用但最后一层未满，不能用 84，只能用，只能用 54=20 次，次， 所以所以 ASL1/12（1720）37/123.083.3.用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? ? 如果要求时间复杂度更小如果要求时间复杂度更小, ,你采用什么方法？此方法的时间复杂度是多少你采用什么方法？此方法的时间复杂度是多少? ? 答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元 素相同时，比较素相同时，比较 1 1 次即可。要想降低时间复杂度，可以改用次即可。要想降低时间复杂度，可以改用 HashHash 查找法。此方法对表内每查找法。此方法对表内每 个元素的比较次数都是个元素的比较次数都是 O O（1 1） 。4.设哈希（设哈希（Hash）表的地址范围为）表的地址范围为 017，哈希函数为：，哈希函数为：H（K）K MOD 16。 K 为关键字，用线性探测法再散列法
