【数据结构】期末考试期中必考试卷及答案.doc

*大学 学院 专业 年级 班 学号 姓名 得分 一、 选择题：（每小题2分，共40分）1. 研究数据结构就是研究 。A) 数据的逻辑结构 B)数据的逻辑结构和存储结构B）数据的存储结构 D)数据的逻辑结构、存储结构及其数据在运算上的实现2. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、 等五个特性。A) 可行性、可移植性和可扩充性 B)可行性、有穷性和确定性C) 确定性、有穷性和稳定性 D)易读性、稳定性和确定性3. 算法分析的目的是 ，算法分析的两个主要方面是 。A) 给出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性E) 空间复杂性和时间复杂性 F) 正确性和简明性G）可读性和文档性 H）数据复杂性和程序复杂性4. 线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 结构。A）随机存取 B）顺序存取 C）索引存取 D）散列存取5. 线性表若采用链式存储结构时，要求内存可用存储单元的地址 。A）必须是连续的 B）部分地址必须是连续的C）一定是不连续的 D）连续不连续都可以6. 在以下的叙述中，正确的是 。A) 线性表的线性存储结构优于链表存储结构B) 二维数组是其数据元素为线性表的线性表C) 栈的操作方式是先进先出D) 队列的操作方式是先进后出7. 线性表L=（a1,a2,an）,下列说法正确的是 。A) 每个元素都有一个直接前驱和一个直接后继B) 线性表中至少要有一个元素C) 表中诸元素的排列顺序必须是由小到大或由大到小D) 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和直接后继8. 对单链表表示法，以下说法错误的是 。A) 数据域用于存储线性表的一个数据元素B) 指针域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针C) 所有数据通过指针的链接而组织成单链表D) NULL称为空指针 ，它不指向任何结点只起标识作用9. 非空的循环单链表head的尾结点*p满足条件 。A) p-next=head B) p-next=NULLC) p=NULL D) p=head10. 在一个单链表中，若删除p所指结点的后继结点，则执行 。A）p-next=p-next-next;B）p=p-next;p-next=p-next-next;C）p-next=p-next;D）p=p-next-next; 11. 在栈操作中，输入序列为（A，B，C，D）， 不可能得到的输出序列是 。A）（A，B，C，D） B）（D，C，B，A）C）（A，C，D，B） D）（C ，A，B，D）12. 设栈S用顺序存储结构表示，则栈S为空的条件是 。A）S.top-S.base0 B）S.top-S.base=0C）S.top-S.basen D）S.top-S.base=n13. 向一个栈顶指针为HS的链栈中插入一个s结点时，执行 。A）HS-next=s; B）s-next=HS-next; HS-next=s;C）s-next=HS; HS=s; D）s-next=HS；HS=HS-next;14. 一个队列的入队序列是1，2，3，4，则队列的输出序列是 。A）4，3，2，1 B） 1，2，3，4 C）1，4，3，2 D）3，2，4，115. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址是 。A）SA+141 B) SA+144 C) SA+222 D) SA+22516. 按照二叉树的定义，具有3个结点的二叉树有 种。A）3 B) 4 C) 5 D) 617. 深度为5的二叉树至多有 个结点。A) 16 B) 32 C) 31 D) 1018. 如下图所示的4棵二叉树中， 不是完全二叉树。 A) B) C) D)19. 在线索化二叉树中，t所指结点没有左子树的充要条件是 。A) t-lchild = NULL B) t-ltag = 1C) t-ltag = 1 且 t-lchild = NULL D) 以上都不对20. 树最适合用来表示 。A) 有序数据元素 B) 无序数据元素C) 元素之间具有分支层次关系的数据 D) 元素之间无联系的数据二、 填空题 (每空 1 分，共 15 分)1. 下面程序段的时间复杂度是 （1） 。 s=0; for(i=0;in;i+) for(j=0;jprior=p-prior; p-prior-next=s; s-next=p; p-prior=s; （4分） (2) L-prior=L & L-next=L （1分）四、稀疏矩阵的三元组表示如下： i j e13221333-1345五、（1）二叉树如下所示：eafdgjcbhi(2) 先序遍历序列：e a d c b j f g h i 中序遍历序列：a b c d j e f h g i 后序遍历序列：b c j d a h I g f e(3)该树的中序线索化二叉树如下所示：eafdgjcbhiNULLNULL （4）此二叉树还原成森林由以下四棵树组成：eadjcbfggi六、赫夫曼树如下： WPL=（2+3）*4+4*3+（7+8+9）*2=8093248733185915七、算法设计题： # define List_Init_Size 100 /线性表存储空间的初始分配量 Status SplitSq(SqList a, SqList &b, SqList &c) b.elem=(Elemtype *)malloc(List_Init_Size*sizeof(Elemtype); c.elem=(Elemtype *)malloc(List_Init_Size*sizeof(Elemtype); if(!b.elem | !c.elem) exit(OVERFLOW); /存储分配失败 b.length=c.length=0; b.