《数据结构与算法》模拟题3答案

发布时间:2023-12-02 13:12:08浏览次数:13
《数据结构与算法》模拟题 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.建立和删除 1/4 10. 已知某二叉树的先序遍历为 A,B,D,C,E,则它可能的中序遍历序列为( )。 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)快速排序四、算法题 3/4 1. 下面算法的功能是:建立一个带有头结点的单链表,链表中存储顺序表中的已有元素。请在空缺处填入相应的语句。void A(LinkList &La, SqList Lb) { La=(LinkList)malloc(sizeof (LNode));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); }}4/4 一、 选择题1、A2、B3、C4、A5、B6、A7、A8、B9、C10、 C11、 C12、 A二、填空题 1. 确定性;2. 数据元素3. 多个;4. 方便运算的实现;5. 先进先出;6. 列序;7. 非零元素;8. ( );9. 完全;10. 0;11. 中序;12.19;三、解答题 1. 5/4 54249153 6 7 830typedef 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,20四、算法题 1. (1) p=La;(2) p->next=q;(3) p=q;6/4 (4) q->next=NULL;2. 以队列作辅助空间,将栈中的元素置逆。7/4
文档格式: docx,价格: 5下载文档
返回顶部