北京交通大学考试试题（A卷）课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇(请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场)一、填空题（每空2分，共20分）1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为的数据结构。
2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。
3. 直接插入排序用监视哨的作用是。
4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算是。
5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。
被比较元素除A[4]外，还有。
6. 在AOV网中，顶点表示，边表示。
7. 有向图G可进行拓扑排序的判别条件是。
8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。
二、选择题（每空2分，共20分）1.在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法2.查找n个元素的有序表时，最有效的查找方法是（）。
A．顺序查找B．分块查找C．折半查找D．二叉查找3.将所示的s所指结点加到p所指结点之后，其语句应为（）。
p(A) s->next=p+1 ; p->next=s;(B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s;4.在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。
A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数5.算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。
A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择6.设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）：Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j7.由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功的平均查找长度是（ ）。
A ．29/11 B. 31/11 C. 33/11 D.35/118.AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。
A. 左、右子树的高度均相同B. 左、右子树高度差的绝对值不超过1C. 左子树的高度均大于右子树的高度D. 左子树的高度均小于右子树的高度9. 下列四种排序方法中，不稳定的方法是（ ）。
A. 直接插入排序B. 冒泡排序C. 归并排序D. 堆排序10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为（ ）。
A ．5B ．6C ．7D ．8 三、 判断题（10分，每小题1分）1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（ ）2. 数组不适合作任何二叉树的存储结构。
（ ）⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=n n n n a a a a a a A ,2,1,2,21,21,13. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。
（ ）4. 在含有n 个结点的树中，边数只能是n-1条。
（ ）5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。
（ ）6. 简单选择排序在最好情况下的时间复杂度为O(n)。
（ ）7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。
（ ）8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置空，因为这会影响以后的查找。
（ ）9. 有n 个数存放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序，其平均查找长度不同。
（ ）10. 广义表中原子个数即为广义表的长度。
( )四、 应用题（24分）1. （6分）将下列由三棵树组成的森林转换为二叉树。
BA DE FCHGJKIL2．(6分)给定下列图，完成以下问题 （1）画出该图的邻接矩阵和邻接表（2）根据所画的邻接表，从顶点B 出发，画出图的深度优先搜索树（3）根据普里姆（Prim ）算法，求它的最小生成树（不必写出全部过程，在生成树中标出边生成的次序即可）1331265 4C B ADEF 5G3．（6分）输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题： （1）构造一棵二叉排序树，计算查找成功的平均查找长度； （2）依此二叉排序树，如何得到一个从大到小的有序序列；（3）画出在此二叉排序树中，删除“66”后的树结构.4. （6分）将序列{25, 34, 12, 7, 15, 47, 65, 79，47+，16 }中的关键字按升序重新排列，请写出（1）冒泡排序一趟扫描的结果（2）以第一个元素为分界点的快速排序一趟扫描的结果（3）堆排序所建的初始堆和第一趟排序结果。
五、程序填空题（10分，每空1分）1.下列算法是建立单链表的算法，请填写适当的语句，完成该功能。
typedef struct Lnode{ElemType data;struct Lnode *next;}LNode, *LinkList;Status CreatList_L(LinkList &L, int n){//正序输入n个元素的值,建立带表头结点的单链线性表LL=(LinkList) malloc(sizeof(LNode));if(!L) return ERROR;L->next=NULL;p= ( 1 ) ;for(i=0;i<n;i++){s=(LinkList) malloc(sizeof(LNode));if(!s) return ERROR;scanf(&s->data);(2) ;(3) ;}p->next=NULL;return OK;}//CreatList_L2. 下列算法是经典模式匹配算法程序，请填写适当的语句，完成该功能。
#define MAXSTRLEN 255typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串长int Index(SString S, SString T, int pos){if(pos>=1&&pos<=S[0]){i=pos; j= (4) ;while(i<=S[0] && j<=T[0])if(S[i]==T[j]) {++i; ++j; }else{(5) ;(6) ;}if(j>T[0]) return (7) ;else return 0;}else return 0;}3.用链表实现的简单选择排序。
设链表头指针为L, 链表无头结点，请填写适当的语句，完成该功能。
void SelectSort(LinkList L){p=L;while(p){q=p; r=q->next;while( r ){if( (8) ) q=r;r= (9) ;}tmp=q->data; q->data=p->data; p->data=tmp;p= (10) ;}}六、算法设计题（16分）算法书写要求：应简单阐述算法的主要思想，对关键变量和关键语句进行注释；如果为递归算法，则应说明递归调用的初始条件，否则扣分。
写出正确的设计思想和伪代码可以酌情给分。
如果算法中用到堆栈，可直接调用下列操作：InitStack(S): 栈初始化push(S,x): 将元素x推入栈S；（插入）pop(S,x): 将栈顶元素存入变量x中；（删除）StackEmpty(S): 判别栈S是否为空，如果是，返回1，否则返回0如果算法中用到队列，可直接调用下列操作：InitQueue(Q): 队列初始化EnQueue(Q,x): 将元素x加入队列Q；（插入）DeQueue(Q,x): 取出队头元素，放入变量x中；（删除）QueueEmpty(Q): 判别队列Q是否为空，如果是，返回1，否则返回01.（8分）已知一个带有头结点的单链表，假设该链表只给出了头指针L。
在不改变链表结构的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，则打印该结点的值，并返回1；否则，只返回0。
（注：如果时间性能达不到要求，但算法思路正确，可酌情给分）链表结构定义为：typedef struct Lnode{ElemType data;struct Lnode *next;}LNode, *LinkList;2、(8分) 下题中任选一题（1）给定一棵赫夫曼树T，编写算法，求该赫夫曼树T的带权路径长度。
赫夫曼树T采用如下定义的存储结构：typedef struct BiTNode{TElemType data; //此处data代表结点的权值struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;（2）假设一棵二叉树以二叉链表表示，元素值为整数，且元素值无重复，编写算法，打印以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。
二叉树T采用如下定义的存储结构：typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;（3）设计一算法，要求将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为head, 二叉树按二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指针，分析算法的时间、空间复杂度。
假设二叉树T采用如下定义的存储结构：typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;2011年数据结构与算法参考答案一、填空题1. O(1) 随机存取2. 803. 防止数组下标越界4. Head【Head【Tail【Tail（LS）】】】5. A[3] A[5] A[7]6. 活动活动之间的先后关系7. 该有向图无环8. DEF二、选择题1.D2.C3.D4.C5.A6.B7.C8.B9.D 10.D三、判断题1.✕2.✕3.✕4.✓5.✕6.✕7.✕8.✓9.✕10.✕四、应用题1.AB DC EGFHIKLJ2. (1) 邻接矩阵：⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞131424162315356355G F E D C B A 邻接表：0123456(2) 深度优先搜索树为：BACEFDG(3)最小生成树：3. (1)二叉排序树如下：33176612255870568760平均查找长度ASL=(1+2X2+4X3+3X4)/10=2.9(2)按照右子树→根节点→左子树的顺序遍历该二叉树，即可得到从大到小的顺序(3)331760122558705687(4)○125、12、7、15、34、47、65、47+、16、79○216、15、12、7、25、47、65、79、47+、34○3初始堆：79、47+、65、34、16、47、12、7、25、15第一趟排序后：65、47+、47、34、16、15、12、7、25、79（二叉树表示方法也可）五、程序填空题1. L2. p->next = s3. p = s4. 15. i = i - j + 26. j = 17. i – j + 18. q->data > r->data9. r->next10. p->next六、算法设计题1. 三种基本思路，（1）设一指针p指向链表的第1个结点，之后找到离p距离为k的结点q（如果有的话），然后p与q同时移动，直到q指向链表尾部。
