发布时间 : 星期五 文章浙大城院数据结构期末模拟4更新完毕开始阅读b60bb820ddccda38376baf6c
模拟试卷4
得分 一．选择题 (本大题共 20 题，每题 1 分，共 20 分)
1．算法的时间复杂度取决于 。
A．问题的规模 B．变量的多少 C．问题的难度 D．A和B 2. 算法能正确的实现预定功能的特性为算法的 。
A. 正确性 B.易读性 C.健壮性 D. 高效性 3．下面程序段的时间复杂度是 。
For(int i=0; i For(int j=0; j A[i][j]=0; A.O(n) B.O(n2) C.O(m+n) D.O(m*n) 4. 数据的物理结构主要包含 这几种结构。 A．顺序结构和链表结构 B．线性结构和非线性结构 C．动态结构和静态结构 D．集合、线性结构、树形结构、图形结构 5. 在下列存储结构中，最适合实现在线性表中进行随机访问的是 。 A. 数组 B. 双向链表 C. 单向链表 D. 循环链表 6. 与单链表相比，双链表的优点之一是 。 A．可以由最后一个结点找到头结点 B．可随机访问 C．插入、删除操作更加简单 D．访问前驱结点更加方便 7．如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 。 A．顺序表 B．单链表 C．双向链表 D．具有表尾指针的循环单链表 8．在表头指针为head且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p->next->next==head，则 。 A. p指向头结点 B. p指向尾结点 C.*p的直接后继是头结点 D.*p的直接后继是尾结点 9．带表头附加结点的单链表head为空的判断条件是 。 A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL 10. 以下不是栈的基本运算的是 。 A．插入元素到栈顶 B. 删除栈底元素 第 1 页 共 5 页 C．判断栈是否为空 D. 将栈置为空栈 11. 若进栈序列为a、b、c、d，进栈过程中可以出栈，则下列不可能的一个出栈序列是 。 A. a, d, c, b B. b, c, d, a C. c, a, d, b D. c, d, b, a 12． 在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是 。 A. f->next=s; f=s; B. r->next=s; r=s; C. s->next=s; r=s; D. s->next=f; f=s; 13. 下列关于线性表、栈和队列的叙述，错误的是 。 A．线性表是给定的n(n必须大于零)个元素组成的序列 B．线性表允许在表的任何位置进行插入和删除操作 C．栈只允许在一端进行插入和删除操作 D．队列只允许在一端进行插入，另一端进行删除 14．下列有关树的概念错误的是 。 A．一棵树中只有一个无前驱的结点 B．一棵树的度为树中各个结点的度数之和 C．一棵树中，每个结点的度数之和等于结点总数减一 D．一棵树中，每个结点的度数之和等于分支数之和 15．下面关于二叉树正确的叙述是 。 A．二叉树中任何一个结点要么是叶子,要么恰好有俩个子女 B．一棵二叉树中结点个数大于0 C．一棵二叉树中叶子结点的个数等于度为2的结点个数加1 D．二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等 16．深度为h的完全二叉树至少有 个结点，至多有 个结点。 A. (2h-1, 2h-1) B. (2h-1-1, 2h-1) C. (2h-1, 2h) D. (2h-1, 2h) 17. 将二叉树B转换成树T后，B中结点的中序遍历次序就是T中结点的 遍历次序。 A.先根 B. 中根 C.后根 D. 层次 18．具有4个顶点的有向完全图，有 条边。 A. 4 B. 6 C. 8 D. 12 19．对某个无向图的邻接矩阵来说，下列叙述正确的是__________。 A. 若矩阵中非零元素个数大大多于零元素个数，则是稀疏图 B. 矩阵中的非零元素个数等于图中的边数 C. 第i行上的非零元素个数和第i列上的非零元素个数一定相等 D. 第i行与第i列上的非零元素的总数等于顶点vi的度数 20．G是一个非连通无向图，共有28条边，则该图至少有 _________ 个顶点。 A. 8 B. 9 C. 29 D. 30 二．填空题 (本大题共 10 个空，每个空 2 分，共 20 分) 得分 1. 数据结构中的非线性结构主要包含 、 两种结构。 2. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括3方面的内容，分 别是数据的逻辑结构、 和操作（运算）。 3．若对线性表进行的操作主要是插入和删除，则该线性表宜采用 存储结构。 第 2 页 共 5 页 4. 在双向链表中，指针p指向某中间结点，若要删除p结点，应执行操作 。 5. 向一个栈顶指针为top的链栈中插入一个指针s所指的结点时，应执行操作 。 6．已知一棵二叉树的中序遍历序列是bgdaehicf，前序遍历序列是 abdgcehif，则这棵二叉树的后序遍历序列是 ，层次遍历序列是 。 7. 在有向图G中，如果对于每一对顶点vi, vj，vi≠vj，若从vi到vj和从vj到vi都存在路径，则称图G是___________。 8. 一个递归的定义可以用递归函数求解，也可以用非递归函数求解，但单从运行时间来看，通 常递归函数比非递归函数 。 三．解答题 ( 本大题共 2 题，每题 6 分，共 12 分) 得分 1．已知一棵树用广义表表示为A(B(C, D), E(F(G, H)), I) ① 请画出这棵树的树形表示法示意图。 ② 设用二叉树方式存储该树，请画出该树的二叉链表存储结构示意图。 2. 设有向图G=(V,E)， V={V0,V1,V2,V3,V4,V5}， E={ 四．程序阅读题 (本大题共 3 题，每题 6 分，共 18 分) 得分 1．阅读下列程序，说明算法的功能，并求出其时间复杂度： int f1(int n) { int i=0, s=0; while (s i++; s=s+i; } return i; } 2. 阅读下列程序，写出算法的功能： int f2(int x[], int n) { if (n==0) return 0; else 第 3 页 共 5 页 return x[n-1] + f2(x,n-1); } 3. 阅读下列程序段，写出程序执行后堆栈的内容（需说明栈顶位置）。 InitStack(S); InitQueue(T); Push(S, ’A’); Push(S, ’B’); Push(S, ’C’); Push(S, ’D’); x=Pop(S); while (!EmptyStack (S)) { EnQueue(T, x); x=Pop(S); } while (!EmptyQueue (T)) { x=OutQueue(T); Push(S, x); } 五．程序填空题 (本大题共 5 个空，每空 2 分，共 10 分) 得分 下列算法是对具有n个顶点的邻接表表示的有向图G，求序号为num的顶点的度。阅读该算法，在空白处填入适当的语句，使该算法完整。 设邻接表结构定义如下： typedef struct node{ int adjvex; struct node *next; } edgenode; typedef edgenode *adjlist[MaxVertexNum]; 算法为： int Degree( adjlist G, int n, int num) { // 求n个顶点的有向图G中顶点号为num的顶点的度，并返回该值。 int sum1=0, sum2=0; edgenode *p; p= ; while (p!=NULL) { //求num的出度 sum1++; p= ; } for (int i=0; i while (p!=NULL) { if (p->adjvex== ) sum2++; 第 4 页 共 5 页 p=p->next; } } return ; } 六．程序设计题 (本大题共 2 题，每题 10 分，共 20 分) 得分 1．设顺序表L非递减有序，请编写高效率算法从L中删除所有其值重复的元素。 如：顺序表L为 (2,3,3,5,7,7,7,8)，执行此算法后L变为(2,3,5,7,8)。 函数原型为：void DelList(List &L) 顺序表结构定义如下： struct List{ ElemType *list; //动态存储空间的基地址 int size; //线性表当前实际长度 int MaxSize; //当前动态数组分配的长度 }; 2．如果两棵二叉树具有相同的树型，则称它们是相似的，如下列两棵二叉树相似。 + a * C b f A B d e 请编写递归函数判断两棵二叉树是否相似，若相似返回1，否则返回0。 函数原型为：int SimilarTrees（BTreeNode *BT1，BTreeNode *BT2） 结点结构定义如下： struct BTreeNode { ElemType data; BTreeNode *left; BTreeNode *right; }; 第 5 页 共 5 页