www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档
32.已知一组键值序列（32，44，38，65，53，42，29，57），试采用堆排序法对该组序列作升序排序，给出建立的初始堆以及第一次输出堆元素后筛选调整的堆。 33.已知一组键值序列（13，12，16，17，15，14，11），试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。
34.若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。
35.若二叉树用二叉链表表示，试编写一算法计算一棵二叉树的叶子总数（可采用递归算法描述）。
全国2007年10月
1.在数据结构中，从逻辑上可以把数据结构分成( ) A.线性结构和非线性结构 C.动态结构和静态结构 2.for（i=0；i for（j=0；j A［i］［j］=i*j； 上面算法的时间复杂度为( ) A.O(m2) C.O(m×n) B.O(n2) D.O(m+n） B.紧凑结构和非紧凑结构 D.内部结构和外部结构 3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( ) A.5 C.7 B.6 D.9 4.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是( ) A.p→llink C.p→llink→llink B.p→rlink D.p→llink→rlink 5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( ) A. 110 C. 100 B. 108 D. 120 6.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( ) A.DCBA B.CDAB 第 6 页 www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档 C.DBAC D.DCAB 7.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( ) A.top++ C.top不变 8.除根结点外，树上每个结点( ) A.可有任意多个孩子、一个双亲 C.可有一个孩子、任意多个双亲 9.题9图中树的度为( ) A.2 B.3 C.5 D.8 题9图 10.有4个顶点的无向完全图的边数为( ) A.6 C.16 B.12 D.20 B.可有任意多个孩子、任意多个双亲 D.只有一个孩子、一个双亲 B.top-- D.top=0 ?011??? 11.设图的邻接矩阵为?001?，则该图为( ) ?010??? A.有向图 C.强连通图 B.无向图 D.完全图 12.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( ) A.静态查找表 C.静态查找表与动态查找表 B.动态查找表 D.静态查找表或动态查找表 13.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是( ) A.线性探测法 C.平方取中法 B.除留余数法 D.折叠法 14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( ) ．．．A.选择排序 B.插入排序 第 7 页 www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档 C.冒泡排序 D.快速排序 15.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( ) A.希尔排序 C.插入排序 B.归并排序 D.选择排序 16.如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为__________型运算。 17.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“__________”。 18.单链表中逻辑上相邻的两个元素在物理位置上__________相邻。 19.在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是__________。 20.设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的__________。 21.若用后根遍历法遍历题21图所示的二叉树，其输出序列为__________。 题21图 第 8 页 www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档 22.具有n个顶点的连通图至少需有__________条边。 23.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__________。 24.设顺序表的表长为n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为__________。 25.在索引顺序表上的查找分两个阶段：一是查找__________，二是查找块。 26.文件的基本运算有检索和修改两类。而检索又有三种方式，它们是__________存取、直接存取和按关键字存取。 27.在对一组关键字为（54，38，96，23，15，72，60，45，83）的记录采用直接选择排序法进行排序时，整个排序过程需进行__________趟才能够完成。 28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为__________。 29.分别写出题29图中二叉树的先根、中根、后根遍历序列。 题29图 30.设要将序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。 31.如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。 题31图 32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时 第 9 页 www.4juan.com 各类考试历年试题答案免费免注册直接下载 全部WORD文档 的访问序列。 题32图 33.对长度为20的有序表进行二分查找，试画出它的一棵判定树。 34.下面程序段为删除循环链表中第一个info域值等于x的结点，请填上程序中缺少的部分。循环链表的结构如题34图所示： 题34图 struct node{ int info;struct node *link; } int Delete (struct node *head, int x) { struct node *p, *q; /*p:当前处理的结点；q：p的前驱结点*/ if (! head ) return (0); if (head→link ==head) { if (head→info==x) { free (head);head=NULL；return (x) } return (0); } p=head; q=head; while (q→link!=head) q=(1) ; while (p→link!=head) { if (p→info==x) { (2) ; if (p==head) head=(3) ; 第 10 页