2008年山东青岛科技大学数据结构考研真题.doc-资料库

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

2008 年山东青岛科技大学数据结构考研真题一、选择题（总分：40 分，每小题 2 分） 1、以下与数据的存储结构无关的术语是（ A．循环队列 B. 链表）。 C. 哈希表 D. 栈 2、在长度为 n 的顺序表的第 i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为 ( ) 。 A. n-i+1 B. n-i C. i D. i-1 3、为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) 。 A. 插入 f( unsigned int 4、下面算法的时间复杂度为( int n ) { if ( n==0 || n==1 ) return else return n*f(n-1); C. 串联接 D. 子串定位 B. 删除 )。 1; } A. O(1) B.O(n) C. O(n2) D.O(n!) 5、三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存储地址为 120，则元素 A[3][4][5]的存储地址为( )。 D. 362 A. 356 6、下列陈述中正确的是( A.二叉树是度为 2 的有序树 B. 358 ) 。 C. 360 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为 2 的结点 D.二叉树中最多只有两棵子树，并且有左右之分 7、假定一棵三叉树的结点数为 50，则它的最小高度为( )。 A. 3 B. 4 C. 5 D. 6 8、已知一个有向图如下图所示，则从顶点 a 出发进行深度优先偏历，不可能得到的 DFS 序列为( )。 A. adbefc B. adcefb C. adcbfe D. adefcb 9、ALV 树是一种平衡的二叉排序树，树中任一结点的( ) 。 A.左、右子树的高度均相同 C.左子树的高度均大于右子树的高度 B.左、右子树高度差的绝对值不超过 1 D.左子树的高度均小于右子树的高度 10、给定一个整数集合{3，5，6，9，12}，下列二叉树哪个是该整数集合对应的哈夫曼（Huffman）树 ( )。

11、在含有 n 个结点的二叉树二叉链表中有（ C. n+1 B. n-1 A. n ）个空链域。 D.（n+1）/2 12、一个栈的输入序列为 123…n，若输出序列的第一个元素是 n，输出的第 i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 13、适用于折半查找的表的存储方式及元素排列要求为( A．链接方式存储，元素无序 C．顺序方式存储，元素无序 14、折半查找的时间复杂性为（） ) 。 B．链接方式存储，元素有序 D．顺序方式存储，元素有序 A. O（n2） B. O（n） C. O（nlog n） D. O（log n） 15、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8， 20，7，15}；则采用的是（ B. 快速）排序。 C. 希尔 D. 冒泡 A. 选择 16、设 a，b 为二叉树上的两个结点，在中序遍历时，a 在 b 前的条件是( )。 A. a 在 b 的右方 B. a 在 b 的左方 C. a 是 b 的祖先 D. a 是 b 的子孙 17、n 个顶点的强连通图至少有( B. n-1 A．n )条边。 C. n+1 D. n（n-1） 18、静态链表中指针表示的是（）。 A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 19、若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 20、执行完下列语句段后，i 值为：（）。 f(int x) ((x>0) ? x* f(x-1):2);} int { return ; int i i =f(f(1)); A．2 二、填空题（总分：30 分，每空 2 分） B. 4 C. 8 D. 无限递归 1、若一个算法中的语句频度之和为 T(n)=3720n+4nlogn，则算法的时间复杂度为________；而下列程序段的时间复杂性的量级则为。

for(i=0;in，则结点 i 无若要在指针 2、在一个不带有头结点的非空单链表中，其结点形式为， q 所指结点之后插入一个 s 指向的结点，则需执行下列语句序列： 3、若按层次顺序将一棵有 n 个结点的完全二叉树的所有结点从 1 到 n 编号，那么当 2i>n, 则结点 i 无：InitStack(s);Push(s,a);Push(s,b);Pop(s)。 4、经过下列运算后 StackTop(s)的值是 5、对称矩阵的下三角元素 a[i,j]，存放在一维数组 v[k]中，k 与 i,j 的关系是 k＝。 6、在有序表（12，24，36，48，60，72，84）中二分查找关键字 72 时所需进行的关键字比较次数为 7、对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为________。 8、已知一个图如下所示，该图最小生成树中各边权值之和为成树中，从顶点 1 到 4 的路径为。查找关键字最多比较的次数 ____ ，在该图的最小生。 data next 。。。 1 10 5 20 11 6 14 9 10 18 2 5 6 4 3 6 9、下列程序中所描述函数 f 的功能为：判断字符串 s 是否对称，对称则返回 1，否则返回 0；如 f("abba")返回 1，f("abab")返回 0；请完成填空，满足功能要求。 int f((1)________) {int i=0,j=0; while (s[j])(2)________; for(j--; i

5、（6 分）给出下图：（1）．画出图的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出图的深度优先生成树和广度优先生成树。 1 2 5 3 8 4 6 7 9 10 6、（6 分）阅读下列算法，并回答下列问题： (1)、该算法采用何种策略进行排序? (2)、写出用此种排序方法对关键字序列{49，38，65，97，76，13，27}排序的过程。 void Sort ( SqList &L ) { for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) { } L.r[0] = L.r[i]; for ( j=i-1; L.r[0].key < L.r[j].key; --j ) L.r[j+1] = L.r[j]; L.r[j+1] = L.r[0]; } 7、（5 分）设有一组关键字｛9，01，23，14，55，20，84，27｝，采用哈希函数：H(key)=key MOD 7，表长为 10，用开放地址法的二次探测再散列方法 Hi=(H(key)+di) MOD 10（di=12， 22，32，…）解决冲突。要求：对该关键字序列构造哈希表，指出有哪些同义词并计算查找成功的平均查找长度。四、算法设计题（总分：40 分）（要求首先用文字描述算法思想，然后用类 c 的语言写出算法）。 1、（6 分）设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B、C，其中 B 表的结点为 A 表中值小于零的结点，而 C 表的结点为 A 表中值大于零的结点（链表 A 的元素类型为整型，要求 B、C 表利用 A 表的结点）。 2、（8 分）函数 void insert(char*s,char*t,int pos)将字符串 t 插入到字符串 s 中，插入位置为 pos。请用 c 语言实现该函数。假设分配给字符串 s 的空间足够让字符串 t 插入。（说明：不得使用任何库函数。 3、（6 分）假设二叉树 T 采用如下定义的存储结构： typedef struct node { DataType data; struct node *lchild,*rchild,*parent;

}PBinTree; 其中，结点的 lchild 域和 rchild 域已分别填有指向其左、右孩子结点的指针，而 parent 域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法，将该存储结构中各结点的 parent 域的值修改成指向其双亲结点的指针。 4、（10 分）采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为 k 的简单路径的算法。 5、（10 分）二叉排序树采用二叉链表存储。编写算法，删除结点值是 X 的结点，要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长（可不考虑被删除的结点是根的情况）。

资料库

2008年山东青岛科技大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料