《数据结构》模拟题.doc

班级 姓名 学号 2011/2012学年第二学期数据结构练习题 一、 单选题（每小题2分，共30分）（1）下列对算法要求不必考虑的是（ ）。A 正确性 B 可读性 C 高效率 D 计算机硬件 （2）当一个函数无返回值时，函数的类型应为（ ）。A. 任意B. voidC. intD. char（3）循环while(i=0) i-；执行次数是（ ）A. 0 B. 1 C. 5 D. 无限（4）在一个单链表HL中，若要在指针p所指结点的后面插入一个由指针q所指向的结点，则执行( )。 A q一next=p一next；p一next=p； B p一next=q一next；q=p； C q一next=p一next；p一next=q； D p一next=q一next；q一next=p；（5）下面程序段的时间复杂度为( )。 for(int i=0; im; i+) for(int j=0; jnext=NULL; C first-next=first; D first!=NULL;（10）在一棵完全二叉树中，若树根结点的编号为0，对于编号为i(i0)的结点，其双亲结点的编号为( )。 A (i+1)/2 B (i-1)/2 C i/2 D i/2-1（11）下列符号中能够作为 C+标识符（变量名）的是_ Aconst B.2a C._shape D.-count（12）有定义： int a5=1,3,5,7,9,*p=a;那么下列表达式中不能得到数值 5 的是（ ） A）a2 B）a3 C）*(p+2) D）*p+4（13）下列陈述中正确的是( )。 A 二叉树是度为2的有序树 B 二叉树中结点只有一个孩子时无左右之分C 二叉树中必有度为2的结点 D 二叉树中最多只有两棵子树，并且有左右之分（14）下面概念中，不属于面向对象概念的是 A)对象 B)继承 C)类 D)过程调用（15）对具有八个元素的序列(49,38,65,97,76,13,27,50)按从小到大排序，( )是直接选择排序法第一趟的结果。A 13,65,38,97,76,49,27,50 B 13,27,38,49,50,65,76,97C 97,76,65,50,49 38,27,13 D 13,38,65,97,76,49,27,50二、填空题（每小题1分，共15分）1. 树的常用存储结构是：双亲表示法、孩子表示法、双亲孩子表示法和_ _。2. 算法效率的估量有两种方法： 和事后统计。3. 在面向对象的程序设计中，将数据和处理数据的操作封装成一个整体就定义了一种事物的类型，称作“类”。类是一种抽象的概念，属于该类的一个实例叫做_。4. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 。5. 在类的对象被创建的时候，_构造_函数会被自动调用。6. 树的带权路径长度最小的二叉树称做 最优二叉树 。7. 深度为k的二叉树至多有 2k-1 个结点。8. 将个函数声明为一个类的友元函数必须使用关键字 friend 。9. 树的深度是指 每个节点孩子的最大数量 。10. 栈是一种 先进后出的特殊 线性表。11. 数据在计算机中的存放方式称为数据的_存储结构_。12. 关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_4844526381091 _。13. 链表是一种采用 链式 存储结构存储的线性表。14. 有序顺序表上的查找算法主要有顺序查找和 链式查找 。15. 插入排序和快速排序，排序方法不稳定的是_快速_。三、判断题（正确的打P，错误的打。每小题2分，共20分）1. 在顺序表中取出第J个元素所花的时间与J大小有关。（ 0 ）2. 任何一棵二叉树中至少有一个结点的度为2。（ 1 ）3. 静态查找表主要有顺序表、有序顺序表和索引顺序表三种结构。（ 1 ）4. 对具有n个元素的序列采用冒泡排序法进行排序，最多需要的排序趟数为n-1。（ 1 ）5. 队列的特点是要求在队头插入数据元素。（ 0 ）6. 线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。（ 1 ）7. 冒泡排序算法在最坏情况下的时间复杂度为0(n)。（ 0 ）8. 将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。（ 0 ）9. 满二叉树一定是完全二叉数，而完全二叉树不一定是满二叉树。（ 1 ）10. 主关键字是能够惟一区分各个不同数据元素的关键字。（ 1 ）四、（6分）已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ，中序遍历的结果序列是EBCDAFHIGJ。（1）画出这棵二叉树并写出后序遍历结果。五、（5分）假定用于通信的电文由8个字母a,b,c,d,e,f,g,h组成，各字母在电文中出现的频率分别为5，15，9，26，10，11，20，4。试为这8个字母设计Huffman编码，并画出相应的Huffman树。六、算法设计题（每小题8分，共24分）1. 为顺序表类（SeqList）编写实现顺序表就地逆置的成员函数，即要求利用原顺序表的存储单元，把数据元素序列（a0,a1,an-1）逆置为（an-1,a1,a0），顺序表类的定义如下。class SeqList protected:DataType * list;int maxSize;int size;public:SeqList(int max=0);SeqList();int Size(void) const;void Insert(const DataType& item,int i);DataType Delete(const int i);DataType GetData(int i)const;2. 利用堆栈和队列的特性编写判断一个字符序列是否是回文的函数，并设计一个主函数对字符序列“ABCDEDCBA”和“ABCDEDBAC”进行测试，堆栈和队列的类定义如下typedef int DataType;const int MaxQueueSize=100;class SeqQueueprivate:DataType dataMaxQueueSize;int front;int rear;int count;public:SeqQueue(void)front=rear=0;count=0;SeqQueue(void)void Append(const DataType& item);DataType Delete(void);DataType GetFront(void)const;int NotEmpty(void)constreturn count!=0;class SeqStackprivate:DataType dataMaxStackSize;int Top;public:SeqStack(void)Top=0;SeqStack(void)void Push(const DataType item);DataType Pop(void);DataType GetTop(void)const;int NotEmpty(void)const return Top!=0;。3. 编写直接插入排序算法的InsertSort函数将若干整数按从小到大排序，（测试用的主函数见下面）。#include typ