2010数据结构试卷C.doc

《2010数据结构试卷C.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、班级学号_________________________姓名___________________（第页，共页）-------------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------

2、----湖南城市学院2009—2010学年第1期《数据结构》试卷C卷时间：120分钟年级专业班级：0906601-02-03【考试】【闭卷】题型一二三四五六七八九十总分分数1020302416得分评卷人：合分人：核查人：一、判断题（每空1分，共10分）1．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中符构成的有限序列。（）2．子串定位函数的时间复杂度在最坏情况下为O（n*m），因此子串定位函数没有实际使用的价值。（）3．KMP算法的最大特点是指主串的指针不需要回溯。（）4．设模式串的长度为m，目标串的长度为n；当n≈m且处理只匹配一次的模式时，

3、朴素的匹配（即子串定位函数）算法所花的时间代价也可能会更为节省。（）5．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）6．链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。（）7．用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（）8．具有12个结点的完全二叉树有5个度为2的结点。（）9．线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）10．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）二、填空题（每空2分，共20分）1

4、．在散列存储中，装填因子的值越大，则____；的值越小，则____。2．中缀表达式9*x+(2.4／5.6-7.3)所对应的后缀表达式为。3．二叉排序树的查找长度不仅与有关，也与二叉排序树的有关。4．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做排序。5．在归并排序中，进行每趟归并的时间复杂度为，整个排序过程的时间复杂度为，空间复杂度为。三、选择题（共30分，每小题3分）1．顺序查找法适合于存储结构为____的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D

5、.索引存储2.对线性表进行二分查找时，要求线性表必须____。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.A.nB.n/2C.(n+1)/2D.(n-1)/24．根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为()。A．O(lon2n)B．O(n)C．O(nlog2n)D．O(n2)5.向具有n个结点的堆中插入一个新元素的时间复杂度为()。A．O(1)B．O(n)C．O(log2n)D．O(nlog2n)6．对

6、长度为3的顺序表进行搜索，若搜索第一个元素的概率为1／2，搜索第二个元素的概率为l／3，搜索第三个元素的概率为l／6，则搜索任一元素的平均搜索长度为()。A．5／3B．2C．7／3D．4／37．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法()。A.正确B.错误8．假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为()个。A．15B．16C．17D．479．按照二叉树的定义，具有3个结点的不同形状的二叉树有()种。A.3B.4C.5D.610．按照二叉树的定义，具有3个不同数据结点的不同的二叉树有()种。A.5B.6C

7、.30D.32班级学号_________________________姓名___________________（第页，共页）-------------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------线--------密--------封--------