《数据结构与算法》模拟题 3一、单选题 1. 计算机算法具有输入、输出和( )这五个特征。A. 可行性、确定性和有穷性 B. 可行性、可移植性和可扩充性C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性2. 线性表中的顺序存储结构是通过何种方式表示元素之间的关系( )。 A.后继元素地址 B.元素的存储顺序 C.左、右孩子地址 D.后继元素的数组下标 3. 最适合描述算法的语言是( )。A.自然语言 B.计算机程序语言C.介于自然语言和程序设计语言之间的伪语言D.数学公式4. 采用链式存储结构存储线性表的优点是( )。A. 便于插入和删除操作 B. 便于随机存取C.花费的存储空间比顺序存储少 D.数据元素的物理顺序与逻辑顺序相同5. 在哈希函数 H(key) = key%m 中，一般来说，m 应取( )。A. 充分大的数 B. 素数 C. 奇数 D. 偶数 6. 在顺序栈中删除元素时，是( )。A. 先删除元素，再移动栈顶指针B. 不分先后，同时进行C. 先移动栈顶指针，再删除元素D. 谁先谁后都可以7. 广义表((a), (b))的表尾是( )。A. ((b)) B.b C.(b) D. ( )8. 设有一个二维数组 A[10][20]，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为 100(十进制)，则元素 A[6][6]的存放位置为( )。A.320(十进制) B. 352 (十进制) C.300(十进制) D. 232 (十进制) 9. 常对数组进行的两种基本操作是( )。A. 查找和插入 B. 插入和修改C. 查找和修改 D.建立和删除 10. 已知某二叉树的先序遍历为 A，B，D，C，E，则它可能的中序遍历序列为( )。 1/4 A.B，C，A，D，E B.C，B，A，D，E C.B，D，A，E，C D.B，E，A，C，D 11. 下面关于图的存储的叙述中，( )是正确的。 A.用邻接表存储图，占用的存储空间数与图中结点个数有关，与边数无关B.用邻接表存储图，占用的存储空间数与图中边数有关，与结点个数无关C.用邻接矩阵法存储图，占用的存储空间数与图中结点个数有关，与边数无关D.用邻接矩阵法存储图，占用的存储空间数与图中边数有关，与结点个数无关12. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。A. 冒泡排序 B. 快速排序C. 直接插入排序 D. 简单选择排序二、填空题 1. 计算机算法具有输入、输出、可行性、有穷性和___________这五个特征。 2. 数据的基本单位是________________。 3. 在图形结构中，每个结点的前驱结点和后继结点可以有____________。 4. 在单链表中，头结点的作用是____________________________。 5. 队列具有____________的特点。 6. 二维数组的两种顺序存储结构分别为以行序为主序的方式和以________为主序的方式。 7. 对于稀疏矩阵的压缩存储只需存储_________________。8. 广义表((a))的表尾是____。9. 对于一个具有 7 个结点的二叉树，当它为一棵________二叉树时具有最小高度。10. 设无向图 G 的顶点数为 n，则 G 最少有________条边。 11. 对二叉排序树进行________遍历，可以得到该二叉树所有结点构成的有序序列。 12. 具有 20 个记录的序列，采用起泡排序最少的比较次数为_____。三、解答题 1. 请用 C 语言给出顺序栈(栈的顺序存储结构)的类型定义。2/4 2. 有字符串序列为“3*-ya/y”，试利用栈将字符串次序改为“3y-*ay/”，请写出操作步骤。(可用 X 代表扫描该字符串过程中顺序取一个字符进栈的操作，用 S 代表从栈中取出一个字符加入到新字符串尾的操作。例如：ABC 变为 BCA，则操作步骤为 XXSXSS)。3. 按行序为主序列出三维数组 A[2][3][2]的所有元素在内存中的存储次序。4. 用 3，6，7，8，30 作为叶子结点的值生成一棵赫夫曼树，并计算该树的带权路径长度。5. 在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数是多少。6. 以关键字序列{12，2，16，9，10，8，20}为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。(1)直接插入排序 (2)快速排序四、算法题 1. 下面算法的功能是：建立一个带有头结点的单链表，链表中存储顺序表中的已有元素。请在空缺处填入相应的语句。void A(LinkList &La, SqList Lb) { La=(LinkList)malloc(sizeof (LNode));3/4 La->next=NULL;(1) ;for (i=0; i<=Lb.length-1; i++){ q=(LinkList)malloc(sizeof(LNode)); q->data=Lb.elem[i]; (2) ; (3) ; } (4) ;}2. 阅读如下算法，给出该算法的功能。void unknow(Stack &S){// Q 是一局部变量---队列 InitQueue(Q); while(!StackEmpty(S)) { i=Pop(S); EnQueue(Q,i); } while(!QueueEmpty(Q)) { i=DeQueue(Q); Push(S,i); }}一、 选择题1、A2、B3、C4、A5、B6、A7、A8、B9、C10、 C11、 C12、 A二、填空题 1. 确定性;2. 数据元素3. 多个;4. 方便运算的实现;5. 先进先出;6. 列序;7. 非零元素;8. ( );9. 完全;4/4 54249153 6 7 83010. 0;11. 中序;12.19;三、解答题 1. typedef struct {SElemType *base;SElemType *top;int stacksize;}SqStack;2. XSXXXSSSXSXXSS。3. 000 001 010 011 020 021 100 101 110 111 120 121 4. 带权路径长度：1025.答案 6 3*2+2*1+x*0=e=n-1=2+1+x-1X=66. (1)直接插入排序：122，122，12，162，9，12，162，9，10，12，162，8，9，10，12，162，8，9，10，12，16，20(2)快速排序：[8，2，10，9] 12 [16，20][2] 8 [10，9] 12，16，202，8，9，10，12，16，205/4 四、算法题 1. (1) p=La;(2) p->next=q;(3) p=q;(4) q->next=NULL;2. 以队列作辅助空间，将栈中的元素置逆。6/4