历年考题数据结构试题卷

1、所谓算法是指 A、计算机程 B、求解特定问题的计算方C、算 D、求解特定问题的指令的有限序2在一个单链表中若p所指结点不是表尾结点在p之后插入s所指结点则执 A、s->nextp;p->nexts;B、s->nextp->next;p->nexts;C、s->next=p->next;p=s;C、p->next=s;s->next=p; A、 B、 C、n-i+1D、不确4、不结点的单链表head为空的判定条件是 A、 B、head-C、head- D、56rearfront0 A、1和 B、2和 C、4和 D、5和6、一棵有124个叶子结点的完全二叉树，最多有 】结点A、 B、 C、 D、7、按照二叉树的定义，具有3个结点的二叉树有 】种A、 B、 C、 D、8、在一个有向图中，所有顶点的入度之和是所有顶点的出度之和的 】倍A、 B、 C、 D、9、对线性表进行二分查找时，要求线性表必须 A、以顺序方式B、以链式方式C、以顺序方式，且结点关键字有序排列D、以链式方式，且结点关键字有序排列10 】个连通分量 12、一棵树有n个结点，在该树的二叉链表表示中，空链域（即空指针域）的个数 A、n- B、2n- C、 D、 A、直接排 B、冒泡排 C、简单排 D、快速排 A、 B、 C、 D、15、在一个包含n个顶点e条边的有向图的邻接矩阵中，零元素的个数为【A、eB、2eC、n2-eD、n2-16、一个栈的入栈序列是1，2，3，4，则栈不可能输出的序列是【A、4321B、1432C、4312D、17、为了将遍历结果还原为惟一的二叉树，应当知道的遍历条件是【D）18、二叉排序树是【19、在有向图的邻接表结构中，顶点v的下标在链表中出现的次数是【 C）顶点v的入 D）依附于顶点v的边20、一个有n个顶点的有向图最多有 】条边A、 B、n(n- C、 D、n(n- 】1、顺序方式结构只能用于线性结构，不能用于非线性结 】2、算法的优劣与描述算法的语言有关 】3、性链表中，只能顺序存取元素，不能直接存取元素 】4、二叉树就是度小于等于2的有序树 号，则对其任意一个编号为i的结点，如果它有左孩子，则其左孩子结点编号为2i 】7、在完全二叉树中，若一个结点没有左孩子，则它必是叶子结点 】8、具有n个顶点的强连通图至少有n条弧 】9、由树转换得到的二叉树，其根结点没有左子树 】10、在二叉排序树中，最大值结点和最小值结点一定是叶子结点 结点的直接后继结点的语句序列 【2 【3 3从堆栈中删除一个数据元素即出栈的操作过程是【4 、【5 4【6 （1…n，链表的第【7】 6、在有n个叶子结点的树中，总的结点个数 【8 7、已知完全二叉树的第7层有8个结点，则该二叉树的叶子结点个数为【9 【12 ，邻接表中所有结点的总数 【13 18个字符：a、b、c、d、e、f、g、h构造出树（要求所有左子树根结点的权值小于等于右子树根结点的权值求出每个字符的编码计算经编码后上述报文的最终长度2、某二叉树的结点数值采用顺序结构，如下图所示，要求F123456789ABCDEFGHJMN23、输入一个正整数序列{40,28,6,72,100,3,54,1,80,91,38}依次上述整数序列中的数据，构造一个二叉排序树画出在此二叉树中删除结点“724写出图（a）ABCABCDEFGHIJKLMNP 45、对于如下所示的图，写出用Kruskal算法构造最小生成树的过程AA924DE853976HF GBC151、L 结点的链表的头指针，以e返回第i个元Status em_L(LinkListL,inti,ElemType{p=L->next; j1; (【1】){【2}if(p==NULL||j>i)returnERROR;e=p->data;returnOK;}//GeoperandTypeEvaluateExpression({ Push(OPTR, c=getchar();while(【3】 { (!In(c,{}

【4c=getchar(switch(【5{)case【6c=getchar(case【7c=getchar(casePop( Pop(OPND, Pop(OPND,【8 【9 voidPostOrderTraverse(BiTreeT,Status(*Visit)( e) //采用二叉链表存贮二叉树，visit()是结点的函Tif(T{【10【11【12} 0。intSearch_Seq(SSTableST,KeyTypekey{【13 //“哨兵for(i=ST.length;【14】;--i【15 //若表中不存在待查元素 }（一）1typedefstructnode{datatypedata;structnode*link;}intAlgo(LinkList{return0;return1+Algo(list-}2voidAlgo(BiTreeT,void(*Visit)({LinkQueueq;QElemTypea;{{EnQueue(&q,a-}}}}（二）3void{StackS;charx,y;x='c';y='k';Push(S,x);Push(S,'a');Pop(S,x);Push(S,'t');Push(S,x);{}}4（3）#defineN4voidmain({SqQueueq; inti,j,e,pre=N,curgroup=0,num=0;intintclash[N],InitQueue(&q); EnQueue(&q,i);//i DeQueue&q,&e);//eif(e<=pre //{ }