《数据结构》期末考试试卷及答案.docx

数据结构期末考试试卷及答案一、简答题（每题5分，共20分）1、具有n个结点的k叉树，若采用k叉链表存储，则空链域有多少个？（要求写出求解步骤）。2、分析二叉排序树的性能（最好、最坏和平均查找性能）。3、希尔排序基本思想。4、图遍历中，设置访问标志数组visited的作用。二、单项选择题（每题1分，共10分）1、 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是（ ）A) -11B) -22C) 12D) 012、 在单链表中，下列说法正确的是（）A) 单链表中头结点是必不可少的； B) 单链表中头指针是必不可少的；C) 在单链表中可以实现随机存取； D) 单链表的存储密度小于顺序表3、假设以数组AM存放循环队列的元素，其头尾指示器分别为front和rear，则当前队列中的元素个数为( )。 A) rear-front+1 B) (rear-front+1)%M C) (front-rear +M)%M D) (rear-front+M)%M4、已知广义表L=(a,b,c),(d,e,f),运用下列（ ）运算可以得到结果：e。A) head（tail(L)） B) tail(head(L)C) head(tail(head(tail(L)D) head(tail(tail(head(L) 5、 线索二叉树中，某结点p是叶子结点,下列（ ）表达式的值为真。A) p-lchild= =NULL B) p-ltag= =1&p-rtag= =1C) p-ltag= =0 D) p-lchild= =NULL& p-rchild= =NULL6、一个具有567个结点的完全二叉树的高度为（ ）A) 9 B) 10 C) 11 D) 127、具有n个顶点的强连通图，至少有（ ）条边 A) n-1 B) nC) n(n-1) D) n(n-1)/28、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A) e B) 2e C) n2-e D)n2-2e9、对关键字序列(20,15,14,18,36,40,10,21) 进行快速排序，以第一个关键字为基准得到的一趟划分后的结果是（ ）。A) (10,15,14,18,20,36,40,21) B) (10,15,14,18,20,40,36,21)C) (10,15,14,20,18,40,36,21) D) (15,10,14,18,20,36,40,21)10、下列四种排序方法中，不稳定的方法是( )。A) 冒泡排序 B) 直接插入排序 C) 归并排序 D) 快速排序三、填空题（每空2分，共20分）1、一个算法中，基本操作的语句频度为(n3+n2log2n+14n)/n2，该算法的时间复杂度为( )2、 65个结点的完全二叉树，按层次，从左到右编号，则最后一个非叶子结点的编号为( )。3、折半查找的两个前提条件分别是（ ）和（ ）4、一个有序表为 4，8，12，16，20，24，28，采用折半查找法查找值为24时需要比较（ ）次。5、有向图的邻接表表示法中，第i条链上边表结点的个数为该顶点的（ ）。6、已知一个带头结点的链栈，其头指针为top；指针s指向一个新结点，要将结点s进栈，则进栈的语句应为：（ ）和（ ）。7、有一种排序算法，其时间复杂度为O（n2），关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定，则该排序算法是（ ）8、对二叉排序树进行中序遍历，会得到一个（ ）序列。四、构造题（每题6分，共30分）1、假定用于通信的某电文仅由8个字母构成，各字母在电文中出现的频率分别为（12，5，3，7，14，21，9，15）。请完成：1）构造哈夫曼树；2）为这8个字母设计不等长的Huffman编码，并计算WPL。2、已知一个图的顶点为A、B、C、D，其邻接矩阵的下三角元素全为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。3、用普利姆算法从顶点A出发，构造图1所示连通网的最小生成树（写出过程）。图14、一个线性序列38，25，74，63，52，48，假定采用散列函数Hash(key)=key%7来计算散列地址，将其散列存储在A09中，采用线性探测再散列解决冲突。构造哈希表，并计算等概率情况下的查找成功和不成功的平均查找长度。5、对序列57，40，38，11，13，34，48，75，6，19，9，7，采用堆排序算法进行递减排序，请构造相应的初始堆即建初堆（只写初堆结果即可）。五、算法设计题（每题10分共20分）注：算法设计题只要求给出描述算法的子函数，不需要编写完整的实现程序。1、在一个带头结点的循环链队列中只有尾指针rear，请给出这种队列的入队和出队操作的实现过程。队列的定义如下： typedef struct Node QueueElementType data; /*数据域*/ struct Node *next; /*指针域*/LinkQueueNode,*LinkQueue;2、假设二叉树上的结点值各不相同，设计一个在二叉树中求值为e的结点的双亲结点。函数名已给出，如下： /*若e有双亲，则返回双亲结点指针；若e是根结点或二叉树中无e结点，则返回NULL*/BiTNode* Parent(BiTree bt，ElemType e) 数据结构期末考试试卷1参考答案一、简答题（5分*4=20分）1、n个结点的k叉树，共nk个链域；分支树为n-1个，即n-1个非链域，则空链域有nk-n+1个2、当二叉排序树的左右子树比较均衡时，查找性能最好，此时时间复杂度为O(nlogn)；当二叉排序树每个结点为单分支时，查找性能最差，与顺序查找类似，此时时间复杂度为O(n2)。但二叉排序的平均查找时间复杂度为O(nlogn)。3、按某个间隔，将待排序记录序列分割成若干个子序列，分别进行直接插入排序；继续缩小间隔，对每个子序列进行直接插入排序；最后再对全部记录进行一次直接插入排序。4、防止重复访问；防止遗漏访问。二、选择题（1分*10=10分）(15) ADDCB(610) BBDBD三、填空题（2分*10=20分）1、O(n) 或O(n+logn) 2、323、元素有序 顺序存储4、25、出度6、s-next=top-next; top-next=s;7、简单选择排序8、递增 或非递减 或从小到大四、构造题（6分*6=30分）1、WPL=21*2+(14+15+9+12+7)*3+(5+3)*4=245 (该哈夫曼树有多种形态)2、3、4、构造的哈希表为：0123456789633825745248ASLsucc=(1+1+1+2+2+4)/6= 11/6ASLuncuss=(2+1+1+6=5+4+3)/7= 22/75、五、算法题（10分*2=20分）1、int EnterQueue(LinkQueue rear,ElemType x) /进队LinkQueueNode *newNode;newNode=(LinkQueue)malloc(sizeof(LinkQueueNode);if(!newNode) return false;newNode-data=x;newNode-next=rear-next;rear-next=newNode;rear=newNode;return true;int DeleteQueue(LinkQueue rear,ElemType *x) /出队if(rear-next=rear) return false;p=rear-next-next;rear-next-next=p-next;*x=p-data; free(p);return true;BiTNode* Parent(BiTree bt,ElemType e) /找e结点的双亲BiTNode *p=NULL;if(bt=NULL) return NULL;if(bt-LChild-data=e | bt-RChild-data=e) /访问根return bt; p=Parent(bt-LChild,e); /在左子树上找if(!p) p=parent(bt-RChild,e) /在右子树上找return p;