《数据结构3题答案(5页).doc》由会员分享，可在线阅读，更多相关《数据结构3题答案(5页).doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-数据结构与算法模拟题3一、单选题 1. 计算机算法具有输入、输出和( )这五个特征。A. 可行性、确定性和有穷性 B. 可行性、可移植性和可扩充性C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性2. 线性表中的顺序存储结构是通过何种方式表示元素之间的关系( )。 A.后继元素地址 B.元素的存储顺序 C.左、右孩子地址 D.后继元素的数组下标 3. 最适合描述算法的语言是( )。A.自然语言 B.计算机程序语言C.介于自然语言和程序设计语言之间的伪语言D.数学公式4. 采用链式存储结构存储线性表的优点是( )。A. 便于插入和删除操作 B. 便于随机存取C.花费的存储空间比顺序存储
2、少 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. 设有一个二维数组A1020，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为100(十进制)，则元素A66的存放位置为( )。A.320(十进制) B. 352 (十进制
3、) C.300(十进制) D. 232 (十进制) 9. 常对数组进行的两种基本操作是( )。A. 查找和插入 B. 插入和修改C. 查找和修改 D.建立和删除 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
4、.用邻接矩阵法存储图，占用的存储空间数与图中边数有关，与结点个数无关12. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。A. 冒泡排序 B. 快速排序C. 直接插入排序 D. 简单选择排序二、填空题 1. 计算机算法具有输入、输出、可行性、有穷性和_这五个特征。 2. 数据的基本单位是_。 3. 在图形结构中，每个结点的前驱结点和后继结点可以有_。 4. 在单链表中，头结点的作用是_。 5. 队列具有_的特点。 6. 二维数组的两种顺序存储结构分别为以行序为主序的方式和以_为主序的方式。 7. 对于稀疏矩阵的压缩存储只需存储_。8. 广义表(a)的表尾是_。9. 对于
5、一个具有7个结点的二叉树，当它为一棵_二叉树时具有最小高度。10. 设无向图G的顶点数为n，则G最少有_条边。 11. 对二叉排序树进行_遍历，可以得到该二叉树所有结点构成的有序序列。 12. 具有20个记录的序列，采用起泡排序最少的比较次数为_。三、解答题 1. 请用C语言给出顺序栈(栈的顺序存储结构)的类型定义。2. 有字符串序列为“3*-ya/y”，试利用栈将字符串次序改为“3y-*ay/”，请写出操作步骤。(可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的操作。例如：ABC变为BCA，则操作步骤为XXSXSS)。3. 按行序为主序列出三
6、维数组A232的所有元素在内存中的存储次序。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)mallo
7、c(sizeof (LNode);La-next=NULL;(1) ;for (i=0; idata=Lb.elemi; (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、 略4、 A5、 B6、 略7、 A8、 B9、 C10、 C11、 C12、 A二、填空题 1. 确定性;2. 数据元素3. 略4. 方便运算的实现;5. 先进先出;6. 列序;7. 略8. ( );9. 完全;10. 0;11. 略12.19;三、解答题 1. typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;2. XSXXXSSSXSXXSS。3. 略4. -第 5 页-