数据结构试题及答案2

中 国 海 洋 大 学 命 题 专 用 纸（首页） 2006学年第 1 学期 试题名称 ： 数据结构B 共 3 页 第 1 页 专业年级： 学号 姓名 授课教师名 分数 选择题(每空2分,共40分) 多叉路口交通灯的管理问题，采用（ ）关系的数据结构 a.集合 b.线性 c.树形 d.图状 （ ）是相互之间存在一种或多种特定关系的数据元素的集合。 a.数据 b.数据元素 c.数据对象 d.数据结构 一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，是指算法的（ ）特性 a.有穷性 b.可行性 c.确定性 d.正确性 下列算法的执行频度为（ ）a.0(n) b.O(n3) c.O(n2) d.O(nlogn) for (l=1;l<+n;++l) for(j=1;j<=n;++j){ c[l][j]=0; } 链表中逻辑上相邻的元素的物理地址（ ）相邻 a. 必定 b.不一定 c.一定不 d.其它 操作系统中的作业调度采用（ ）结构 a.顺序表 b.栈 c.队列 d.图 （ ）是由零个或者多个字符组成的有限序列。 a.数组 b.文本 c.线性表 d.字符串 设s=’I AM A STUDENT’ , t=’GOOD’ , q=’WORKER’则 Concat(Substring(s,6,2),Concat(t,Replace(s,’STUDENT’,q)))=( ) a. A GOODWORKER b. ST GOODSTUDENT c. A GOOD STUDENT d.A GOOD WORKER 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A[14]第一个字节的位置（ ） a.1018 b.1024 c.1030 d.1072 三元组用来存储（ ） a.稠密矩阵 b.稀疏矩阵 c广义表 d.特殊矩阵 广义表GetHead[GetTail[GetHead[((a,b),(c,d))]]]操作的结果为（ ） a. b b. (b) c. d d.(d) 广义表（（（））,a,((b,c),(),d),(((e)))）的长度为（ ） a.3 b.4 c.5 d.2 深度为i的二叉树至多有( )结点 a. 2i-1 b. 2i-1 c.2i d.2i-2 授课教师 命题教师或命题负责人 签 字 院系负责人 签 字 年 月 日 中 国 海 洋 大 学 命 题 专 用 纸（附页） 2006学年第 1 学期 试题名称 ：数据结构 共 3 页 第 2 页 已知一棵树边的集合为{, , , , , , , , , , , , },问这棵树的根结点为( )结点G的双亲结点为( )将此树转化为二叉树后，E的左孩子为（ ）B的右孩子为（ ） a.A b. C c. I d.B 已知一棵树的先根次序访问序列为GFKDAIEBCHJ;数的后根次序访问序列为DIAEKFCJHBG。请问这棵树中结点I的双亲为( ),结点H的双亲为( ) a.A b.B c. C d.D 下图中结点B的出度为( ) a. 0 b. 1 c. 2 d.3 填空题(每空4分,共20分) Void conversion(){ //对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数 InitStack(S); Scanf (“%d”,N); While(N){ ( ); N=N/8; } While(!StackEmpty(s)){ ( ); Printf(“%d”, e); } }conversion Status ListDelete_L(LinkList &L, int i, ElemType &e){ //在带头结点的单链线性表L中,删除第i个元素,并由e返回其值 P=L; j=0; While(P->next&&jnext||j>i-1) return ERROR; //删除位置不合理 Q=P->next; ( ) //删除并释放结点 e=Q->data; ( ) return OK; }//ListDelete 中 国 海 洋 大 学 命 题 专 用 纸（附页） 2006学年第 1 学期 试题名称 ：数据结构 共 3 页 第 3 页 三、 从空树开始，按下列插入顺序：DEC、FEB、NOV、OCT、JUL、SEP、AUG、APR、MAR、MAY、JUN、JAN，给出最终所得到的二叉平衡树。（10分） 四、出一组关键字（12，2，16，30，8，28，4，10，20，6，18），按从小到大顺序，写出对其进