精品暨阳学院计算机科学与技术专业《数据结构与算法》科目期末试卷精品.pdf

2022年浙江农林大学暨阳学院计算机科学与技术专业《数据结构与算 法》科目期末试卷A （有答案） 一、选择题 1、n个结点的完全有向图含有边的数目（ ）。 A.n*n B.n(n+1) C.n/2 D.n*(n-1) 2、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为 （ ）。 A.5 B.6 C.8 D.9 3、线性表的顺序存储结构是一种（ ）。 A.随机存取的存储结构 顺序存取的存储结B. 构 C.索引存取的存储结构 存取的存储结D.Hash构 4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛V1，V2， V1，V3，V1，V4，V2，V5，V3，V5， V3，V6，V4，V6，V5，V7， V6，V7｝，G 的拓扑序列是（ ）。 A.V1，V3，V4，V6，V2，V5，V7 ，V3B.V1，V2，V6，V4，V5，V7 C.V1，V3，V5，V2，V6，V7 ，V2，V5，D.V1V3，V4，V6，V7 5、向一个栈顶指针为 h 的带头结点的链栈中插入指针 s 所指的结点时，应执行（ ）。 A.h-next=s B.s-next=h C.s-next=h;h-next=s D.s-next=h-next;h-next=s 6、下列关于无向连通图特性的叙述中，正确的是（ ）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减 1Ⅲ．至少有一个顶点的度为1 A．只有 Ⅰ ．只有B Ⅱ ．CⅠ和 Ⅱ ． ⅠD和Ⅲ 7、下列叙述中，不符合 m阶B树定义要求的是（ ）。 A．根结点最多有 m棵子树 ．所有叶B 结点都在同一层上 C．各结点内关键字均升序或降序排列 ．叶D 结点之间通过指针链接 8、设X是树T 中的一个非根结点，B是 T所对应的二叉树。在 B 中，X 是其双亲的右孩 子，下列结论正确的是（ ）。 A.在树T 中，X是其双亲的第一个孩子 B.在树T 中，X 一定无右兄弟 C.在树T 中，X 一定是叶结点 D.在树T 中，X 一定有左兄弟 9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中 有（ ）个叶子。 A.log n （nB.－1）/2 C.logn+1 （D.n＋1）/2 2 2 10、对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是： A.05，46，13，55，94，17，42 B.05，13，17，42，46，55.94 C.42，13，94，05，55，46，17 D.05，13，46，55，17，42，94 二、填空题 11、无用单元是指______，例______ 12、有向图G=(V，E)，其中 V(G)={0，1，2，3，4，5｝，用a，b，d 三元组表示弧a， b及弧上的权d。E(G)为E(G)= ｛0，5，100，0， 2，10，1，2，5，0，4，30， 4，5，60，3，5，10，2， 3，50，4，3，20｝，则从源点 0到顶点 3的最短 路径长度是______，经过的中间顶点是______。 13、已知有序表为 （12，18，24，35，47，50，62，83，90，115， 134 ）当用二分法查 找 90 时，需______次查找成功，查找 47 时______成功，查找 100 时，需______次才能确 定不成功。 14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的 次序进行排序，若采用初始步长为4 的希尔排序法，则一趟扫描的结果是______ ；若采用 以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。 15、在一棵 m 阶B-树中，若在某结点中插入一个新关