数据结构2007A

（首 页） 试题纸 课程名称： 数据结构（A） 适用专业年级： 07级计算机专业、软件专业 考生学号： 考 生 姓 名： ??????????????????????????????????????????????? 一、选择题（15×2分＝30分） 1、一个算法的时间复杂度为（3n+2nlogn+4n-7）/(5n), 其数量级表示为（ )。 A．O(n) B．O(n) C．O(logn) D．O(1) 2、链表不具有的特点是( )。 A. 可随机访问任一元素 B. 插入删除元素时不需移动 C. 不必事先估计存储空间 D. 所需空间与表长成正比 3、若一个栈的输入序列为abcde，则( )是可能的栈的输出序列。 A. bcdae B. edbca C. aebcd D. cabde 4、表达式a*(b+c)-d的后缀表达式是( )。 A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 5、循环队列用数组A[1..n]存放其元素值，已知其头尾指针分别是f和r，则队列满的条件是( )。 A. r+1==f B. (r+1)%n==f C. (r+1)%n+1==f D. (r%n)+1==f 6、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 7、已知广义表A=(a,b), B=(A,A),则运算head(head(tail(B )))=( )。 A. a B. A C. (a) D. (A) 8、若完全二叉树的结点总数为偶数，则度为1的结点有( )个。 A. 0 B. 1 C. 2 D. 不确定 9、一个二叉树具有（ ）种基本形态。 A. 4 B. 5 C. 6 D. 7 10、已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（ ）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 11、下述编码中哪一个不是前缀码（ ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 12、n个顶点的有向图G 最多有( )条弧。 A. 0 B．n(n-1) C. n D．n(n-1)/2 13、求图中一个顶点到其它各个顶点最短路径的算法是（ ）。 A．Kruskal算法 B．Prim算法 C．Dijkstra算法 D．Floyd算法 14、要进行折半查找，则线性表（ ）。 A. 必须以顺序方式存储 B. 必须以链式方式存储 C. 既可以以顺序方式存储，也可以链式方式存储 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。 22（附 1 页 ） D. 必须以顺序方式存储，且数据已按递增或递减顺序排好 15、对于具有144 个记录的文件，若采用分块查找，且每块长度为8，则平均查找长度为（ ）。 A. 14 B. 15 C. 16 D. 17 二、判断题 （10×2分=20分） （ ）1、所谓数据的逻辑结构是指数据元素之间的逻辑关系。 （ ）2、线性表的长度是线性表所占用存储空间的大小。 （ ）3、栈和队列都是运算受限的线性表。 （ ）4、一维数组的逻辑结构是线性结构，存储结构是顺序存储表示。 （ ）5、二叉树是每个结点最多只有二个子树的树。 （ ）6、由树转换成的二叉树中，根结点的右子树总是空的。 （ ）7、若无向图G中各顶点的度均大于或等于2，则G中必有回路。 （ ）8、在用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 （ ）9、任何一个关键活动提前完成，那么整个工程都将会提前完成。 （ ）10、如果只想在一个有n个元素的任意序列中得到其中最小的第k（k<next; ????????????????????(1分 ) s->next=L;L=s; ????????????????????(2分 ) } } 2、求二叉树宽度（10分） int width(BiTree T){ BiTree P=T, q[M]; ????????????????????(1分 ) int front=-1, rear=-1，count=0, right，max=0; ??????????(1分 ) if (P!=NULL) {q[++rear]=P; max=1; right=rear;} ??????????????(2分 ) while (front!=rear) ????????????????????(5分 ) { P=q[++front]; if (T->lchild!=NULL) {q[++rear]= T->lchild; count++;} if (T->rchild!=NULL) {q[++rear]= T->rchild; count++;} if (front==right) {if (max < count) max=count; count=0; right=rear; } } return(max); ????????????????????(1分 ) } 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。

（附 5 页 ） i++;j--; } } （2）用带头结点的单链表作存储结构 Void InvertLinkList(LinkList &L) { p=L;L=NULL; ????????????????????(1分 ) while(p){ ????????????????????(1分 ) s=p;p=p->next; ????????????????????(1分 ) s->next=L;L=s; ????????????????????(2分 ) } } 2、求二叉树宽度（10分） int width(BiTree T){ BiTree P=T, q[M]; ????????????????????(1分 ) int front=-1, rear=-1，count=0, right，max=0; ??????????(1分 ) if (P!=NULL) {q[++rear]=P; max=1; right=rear;} ??????????????(2分 ) while (front!=rear) ????????????????????(5分 ) { P=q[++front]; if (T->lchild!=NULL) {q[++rear]= T->lchild; count++;} if (T->rchild!=NULL) {q[++rear]= T->rchild; count++;} if (front==right) {if (max < count) max=count; count=0; right=rear; } } return(max); ????????????????????(1分 ) } 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。

本文来源：https://www.bwwdw.com/article/ap85.html