2011广西壮族自治区数据结构与算法考资料

1、4、void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next; //把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse2、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.3、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。

但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。

void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。

{if(h1>=l1){post[h2]=pre[l1]; //根结点half=(h1-l1)/2; //左或右子树的结点数PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列} }//PreToPost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。

设置前驱结点指针pre，初始为空。

第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。

1、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。

A）p->next=p->next->next; B） p=p->next;C）p=p->next->next; D） p->next=p;2、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C） C D） D3、串的逻辑结构与（ D ）的逻辑结构不相同。

A）线性表 B）栈C）队列 D）集合4、线性表的链接实现有利于（ A ）运算。

A）插入 B）读元素C）查找 D）定位5、线性表的链接实现有利于（ A ）运算。

A）插入 B）读元素C）查找 D）定位6、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的7、数据结构中，在逻辑上可以把数据结构分成（ B ）。

A）动态结构和静态结构B）线性结构和非线性结构C）紧凑结构和非紧凑结构D）内部结构和外部结构8、线性表的链接实现有利于（ A ）运算。

A）插入 B）读元素C）查找 D）定位9、线索二叉树中某结点D，没有左孩子的条件是（ B ）。

A）D->Lchild=Null B) D->ltag=1C) D->Rchild=Null D) D->ltag=010、已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A) 5，4，3，2，1，6 B) 2，3，5，6，1，4C) 3，2，5，4，1，6 D) 1，4，6，5，2，311、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。

A）9 B）11 C）15 D）不能确定12、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。

1、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。

A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]2、广义表head(((a,b),(c,d)))的运算结果为（ A ）。

A）(a,b) B）(c,d)C）空表 D）（（a,b）,(c,d)）3、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。

A）p->next=p->next->next; B） p=p->next;C）p=p->next->next; D） p->next=p;4、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。

A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c5、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。

A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c6、下面关于线性表的叙述中，错误的是哪一个？（ D ）A）线性表采用顺序存储，必须占用一片连续的存储单元。

B）线性表采用链接存储，便于插入和删除操作。

C）线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用顺序存储，便于进行插入和删除操作。

7、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。

A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;C）p->next=s->next; s->next=p D）p->next=s; s->next=q;8、链式存储的存储结构所占存储空间（ A ）。

《数据结构》考试题（闭卷）A卷（电信系本科2011级2012年11月30日）姓名班级学号注：总分110分，不折算，超过100分按100分计一、回答下列问题 (每题4分，共36分)1．“算法的优劣与算法描述语言无关，但与所用计算机有关”这句话对吗？简单说明理由。

2. 设一模式串为“aabbccdaabccd”，求其next函数。

next函数中定义Max {k | 1<k<j,且’p1…p k-1’=’p j-k+1…p j-1’}，为什么需要定义求最大的k值？3．有n个结点的二叉树采用顺序存储结构存储，何种情况下最节省存储空间？，何种情况下最浪费存储空间？4．把一颗二叉排序树结点由大到小输出，基本的方法是什么？5．已知某二叉树按层次遍历序列为ABCDEFGHIJ，中序遍历序列为DBGEHJACIF，a)画出该二叉树；b)给出其先序遍历序列6．在哈夫曼编码中，有两个符号A、B的权重相等（A在B前面），若采用稳定的排序方法从小到大排序，请问A、B两个符号的编码长度哪个长？并请说明原因。

7．如图所示二叉排序树的查找成功和查找不成功的平均查找长度是：8. 对序列{12，9，7，8，20，-3，4}进行排序，进行一趟后数据的排列变为{4，9，-3，8，20，7，12}；则采用的是（）排序。

A. 选择B. 快速C. 希尔D. 冒泡9．给定一序列. 求n在什么范围内，该序列是一个堆。

二、综合题（共34分）1. 下面是一个冒泡排序算法，但效率不高，请给出改进思路，并写出改进算法，让其效率提高。

(8分)Void ABC (List & L){ pass=0 ;For(i=1;i<=n-1){Pass++ ;For (j=i;j<=n-pass ，j++){if L[j].key>L[j+1].keyL[j] ←→ L[j+1]}}}2．已知带权连通图G ＝(V ，E)的邻接链表如下图所示。

广西工学院2010 —2011 学年第1 学期考试试题考核课程数据结构与算法（ B 卷）考核班级计y091~096学生数215 印数230 考核方式闭卷考核时间120 分钟【说明】试题满分共100分；考试时间为2个小时；一、选择题（每小题2分，共30分）1、数据的基本组成单位是。

A、数据项B、数据类型C、数据元素D、数据变量2、若进栈序列为1,2,3,4,假定进栈和出栈可以穿插进行，则可能的出栈序列是。

A. 2,4,1,3B. 3,1,4,2C. 3,4,1,2D. 1,2,3,43、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。

A. (rear-front+m) MOD mB. rear – front + 1C. rear-front-1D. rear-front4、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是。

A. acbedB. deabcC. decabD.cedba5、已知某二叉树中，有n0个叶节点，n1个度为1的节点，n2个度为2的节点。

则：n0= 。

A、n1+1B、n2+1C、n1+n2 D、n1+2n26、高度为5的二叉树至多有个节点。

A. 16B. 32C. 31D. 107、设某程序的执行时间T(n)=3n2 + log2n + (2/3)n，则其时间复杂度为。

A、T(n)=O(3n2)B、T(n)=O(n2)C、T(n)=O (log2n)D、T(n)=O (2/3)n8、下面的序列中，是堆。

A、1，2，8，4，3，9，10，5B、1，5，10，6，7，8，9，2C、9，8，7，6，4，8，2，1D、9，8，7，6，5，4，3，79、用某种排序方法对线性表（84，47，25，15，21）进行排序时，结点序列的变化如下：（1）84 47 25 15 21（2）15 47 25 84 21（3）15 21 25 84 47（4）15 21 25 47 84那么，这里所采用的排序方法是。

全国高校计算机联合考试(广西考区)一级笔试试题卷2011年6月25日闭卷考试考试时间：60分钟试卷种类：[A]考生注意：①本次考试试卷种类为[A]，请考生务必将答题卡上的试卷种类栏中的[A]方格涂黑。

②本次考试全部为选择题，每题下都有四个各选答案，但只有一个是正确的或是最佳的答案。

答案必须填涂在答题卡上，标记在试题卷上的答案一律无效。

每题只能填涂—个答案，多涂本趣无效。

@请考生务必使用2B铅笔按正确的填涂方法，将答题卡上相应题号的答案的方格涂黑。

④请考生准确填涂准考证号码。

⑤本试卷包括第一卷和第二卷。

第一卷各模块为必做模块；第二卷各模块为选做模块，考生必须选做其中一个模块，多选无效。

第一卷必做模块必做模块一计算机基础知识(每项l.5分，14项，共21分)一、以二进制和程序控制为基础的计算机结构是___1___提出的。

目前电子计算机已经发展到__2____阶段。

1．A．布尔B．冯．诺依曼c．巴贝奇D．图灵2 ．A．晶体管电路B．集成电路c．大规模和超大规模集成电路D．电子管电路二、计算机系统由__3____ 组成。

硬件系统包括运算器、__4___ 、存储器、输入和输出设各3．A．硬件系统和软件系统B．硬件系统和程序C．主机、显示器、鼠标和键盘D．系统软件和应用软件4．A．显示器B．磁盘驱动器C．控制器D．鼠标器三、下列存储器中，_5___ 是利用磁存储原理来存储数据的。

下列有关存储器读写速度快慢排列顺序正确的是__6___。

5．A．CMOS B．光盘c．DVD光盘D．硬盘6．A．RAM>cache>硬盘>光盘B．cache>RAM>硬盘>光盘C．cache>硬盘>RAM>光盘D．RAM>硬盘>光盘>cache四、计算机硬件能够直接识别和执行的语言是__7___。

C#属于__8___。

7．A．机器语言B．汇编语言C．高级语言D．低级语言8．A．机器语言B．汇编语言C．高级语言D．低级语言五、在计算机使用过程中，关于“死机”现象的解释是__9___ 。