数据结构模拟试卷1

数据结构模拟试卷1(总分：44.00，做题时间：90分钟)一、单项选择题(总题数：12，分数：24.00)1.(江苏大学)下面关于串的叙述中，( )是不正确的。

A.串是字符的有限序列B.空串是由空格构成的串√C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储选项A：串是零个或多个字符组成的有限序列，一般记为：S=''a 1 a 2…a n "，S称为串名，双引号括起来的字符序列是串值，将串值括起来的双引号本身不属于串，它的作用是避免串与常数或标识符混淆，故A选项正确。

选项B：窒皇是指长度为零的串，它不包括任何字符。

但是考生要注意与空白串进行区分，空白串是指由一个或者多个空格组成的串，故B选项错误。

选项C：模式匹配是一个比较复杂的串操作，是子串在主串中的定位操作。

常用的模式匹配算法有朴素的原始匹配算法和经过优化改进的无回溯算法，故C选项正确。

选项D：串是特殊的线性表，所以串的存储结构与线性表的存储结构类似。

串的顺序存储结构简称顺序串，顺序串又可按存储分配的不同分为静态存储分配的顺序串和动态存储分配的顺序串。

串的链式存储就是用单链表的方式存储串值，故D选项正确。

2.(华中科技大学)若串S="bioinformatics''，其子串的个数是( )。

A.15B.95C.35D.106 √对于长度为n的字符串来说，其子串的个数为{n(n+1)／2}+1(最后+1是因为空串是任何串的子串)，记住即可。

此题n=14，所以其子串的个数是106。

3.(中国科学院)串是一种特殊的线性表，其特殊性体现在( )。

A.数据元素是一个字符√B.可以顺序存储C.数据元素可以是多个字符D.可以链式存储选择这道题的原因是它被多所学校(武汉大学、中科院、大连理工、江苏大学等)原题考查，考生只需记住一句话：串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。

数据结构模拟考试题一 一、解答题（共30分） 1.（6分）已知一棵二叉树的后序遍历和中序遍历序列，求该二叉树的先序遍历序列。

后序遍历序列：DBGHFECA 中序遍历序列：BDACGFHE

2.（6分）设一无向图的邻接表如下：

写出从顶点J开始，分别进行“深度优先”和“广度优先”遍历的结果。 3.（8分）设有关键字集合K={18,22,44,13,20,36,25,44,35,51,41,15}采用散列存储结构，哈希表为HT[0…12]，设哈希函数H(K)=K%13，用拉链法解决冲突，构造出相应的散列表。

4.（10分）假设用于通讯的电文仅由8个字母组成，字母在中文中出现的频率分别为：7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

二、填空题（每小题2分，共20分） 1.对于一个长度为n的顺序表，在表头插入元素的时间复杂度为( )，在表尾插入

元素的时间复杂度为( )。 2. 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是

（ ）。 3. 在以first为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分

别为: ( )和( )。

4. 设元素A,B,C,D,E依次进栈，若要在输出端得到序列A C D B E，则应进行的操作序列为Push(S,A),Pop(S), Push(S,B),Push(S,C),( ）,（ ）, （ ），Pop(S), Push(S,E),Pop(S)。 5. 线性结构的逻辑特征是（ ）。 6.折半查找技术适用于存储结构为（ ）的线性表，并且表中的元素必须是

（ ）。 7.任何连通图的连通分量只有一个，即是（ ）。 8.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，用希尔排序(d1=5,d2=3,d3=1)，第二趟的排序结果是（ ）。 9.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，用快速排序方法，第二趟的排序结果是（ ）。 10.数据结构的内涵包括（ ）、（ ）和（ ）

数据结构模拟试题一一、单选题（每小题2分，共8分）1、在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移个元素。

A n-iB n- i十1C n-j-1 C i2、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为。

A O（1）B O（n）C O（n2）D O（1og2n）3、假定一个顺序队列的队首和队尾指针分别为1和r，则判断队空的条件为。

A f+ 1= =rB r＋1= =fC f= =0D f= =r4、从堆中删除一个元素的时间复杂度为。

A O（1）B O（n）C O（1og2n）D O（nlog2n）二、填空题（每空1分，共32分）1、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着、和的联系。

2、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为，若假定p为一个数组a中的下标，则其后继结点的下标的。

3、在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为参数。

4、栈又称为表，队列又称为表。

5、后缀表达式“4 5+3*2 4+ *”的值为。

6、一棵深度为5的满二叉树中的结点较为个，一棵深度为3的满四叉树中的结点数为个。

7、对于一棵含有40个结点的理想平衡树，它的高度为。

8、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明，若元素的值小于根结点的值，则继续向查找，若元素的大于根结点的查找。

9、当从一个小根堆中删除一个元素时，需要把元素填补到位置，然后再长条件把它逐层调整。

10、对于一个具有n个顶点的图，若采用邻接炬阵表示，则矩阵大小为。

11、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为和。

12、二分查找过程所对应的判定树既是一棵，又是一棵。

13、若长度n=10000的线性表进行二级索引存储：每级索引表中的索引项是下一级20个记录的索引，则一级索引表的长度为，二级泵引表的长度为。

专科《数据结构》摹拟题试卷一. (共50 题,共100 分)1. 数据的逻辑结构在计算机内部存储表示称为为数据的() 。

(2 分)A.数据结构B.逻辑关系C.物理结构D.数据元素的内部结构★检查答案标准答案：C2. ()是数据的不可分割的最小单位。

(2 分)A.数据对象B.数据元素C.数据类型D.数据项★检查答案标准答案：D3. 算法的时间复杂度是对算法()的度量。

(2 分)A.时间效率B.空间效率C.可读性D.茁壮性★检查答案标准答案：A4. ()是限制了插入和删除操作在一端进行的线性表。

(2 分)A.栈B. 队列C.串D.数组★检查答案标准答案：A5. 数组通常采用顺序存储的优点是() 。

(2 分)A.便于增加存储空间B.便于依据下标进行随机存取C.避免数据元素的挪移D.防止下标溢出★检查答案标准答案：B6. 采用带头结点双向链表存储的线性表，在插入一个元素时，需要修改指针 () 次。

(2 分)A.1B.2C.3D.4★检查答案标准答案：D7. 线性表的顺序存储结构是一种()的存储结构。

(2 分)A.顺序存取B.随机存取C.索引存取D.Hash 存取★检查答案标准答案：B8. 数组a[1..256]采用顺序存储，a 的首地址为10，每一个元素占2 字节，则a[21] 的地址是()。

(2 分)A. 10B.30C.50D.70★检查答案标准答案：C9. 深度为4 的二叉树，第4 层至少有()个结点。

(2 分)A.0B.1C.8D. 15★检查答案标准答案：B10. 若二叉树对应的二叉链表共有11 个非空链域，则该二叉树有()个结点的二叉树。

(2 分)A.10B.11C.20D.21★检查答案标准答案：A11. 下面叙述错误的是() 。

(2 分)A.借助于队列可以实现对二叉树的层遍历B.栈的特点是先进后出C.对于单链表进行插入操作过程中不会发生上溢现象D.在无向图的邻接矩阵中每行1 的个数等于对应的顶点度★检查答案标准答案：C12. 以下与数据的存储结构无关的术语是()。

第3章栈和队列一选择题1. 对于栈操作数据的原则是（ B. 后进先出）。

2. 在作进栈运算时,应先判别栈是否(①B. 满),在作退栈运算时应先判别栈是否(②A. 空)。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③B. n)。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 (④D. 栈底)分别设在这片内存空间的两端,这样,当(⑤C. 两个栈的栈顶在栈空间的某一位置相遇)时，才产生上溢。

3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（B. n-i+1）。

4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（D. 不确定的）。

5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是(D. 不确定)。

6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（C. 3 4 6 5 2 1）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 67. 设栈的输入序列是1，2，3，4,则（D. 4，3，1，2，）不可能是其出栈序列。

A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，E. 3，2，1，4，8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（B.5 4 1 3 2）。

9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D. 3 2 1 5 4）。

10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（D. d, c，a，b）。

A. a，c，b，dB. b, c，d，aC. c, d，b, aD. d, c，a，b11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（D. cabdef）。

数据结构模拟题1一、判断题。

判断下列各题是否正确，若正确，在答题卡中涂“A”，否则涂“B”。

1．数据的存储结构也称为物理结构，指数据的逻辑结构在计算机中的映象，它包括数据元素的映象和数据元素关系的映象。

√2．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。

Χ3．在顺序表中，插入和删除时移动元素的个数与该元素的位置有关。

√4．链表的每个结点中都恰好包含一个指针。

Χ5．链表只能借助于指针和动态变量来实现。

Χ6．对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

√7．若一个队列入队的次序为1234，则出队的次序也一定是1234。

√8．若一棵二叉树的任意一个非叶子结点的度都为2，则该二叉树是满的。

Χ9．二叉树中所有结点个数是2k-1-1，其中k是树的深度。

Χ10．用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

√11．满二叉树不一定是完全二叉树。

Χ12．使用递归也可以实现二叉树的先序、中序和后序遍历。

√13．对二叉排序树进行中序遍历得到的序列是由大到小的。

14．哈夫曼树是带权路径长度最小的二叉树，路径上权值较大的结点离根较近。

√15．邻接表存储结构只用于有向图的存储，邻接矩阵对有向图和无向图的存储都适用。

Χ二、单选题。

1．数据的最小单位是【】。

AA、数据项B、数据类型C、数据元素D、数据变量2．从逻辑上可以把数据结构分为【】两大类。

CA、动态结构、静态结构B、顺序结构、链式结构C、线性结构、非线性结构D、初等结构、构造型结构3．【】不是要关注程序的时间复杂性的原因。

BA、确定程序运行时间的上限B、判断一个计算机系统是否有足够的内存来运行该程序C、正在开发的程序可能需要提供一个满意的实时响应D、在多种可选的方案中决定采用哪一个4．【】是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性数据结构。

CA、线性表B、栈C、队列D、树5．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为【】。

《数据结构与算法》模拟卷（1）答案）二、选择题（共20 空，每空 1.5 分，共30 分）三、填空题（共19 空，每空 1-2 分，共23 分）1.设每个元素需要4个字节，顺序存储1200个元素；若首地址是2000，那么第150个元素的地址是____2596___。

(每空 2 分)2.已知两个字符串s1=”Data structure is very useful.”, s2=”uct”, 那么s1的长度 strlen(s1)=____30/31/32___, s2是否为空的判断StrEmpty(s2)=_false_, 子串Substr(s1,16,2)=____is___, 查找子串的位置Index(s1,s2,1)=__9__。

3.下列表示的图中，共有__5__个是树；有__1___个是满二叉树；有___2__个是完全二叉树。

4.下列二叉树的中序遍历序列是______D B N G O A E C_______;后序遍历序列是________D N O G B E C A__________。

(每空 2 分)5.5个顶点的无向图，若要求其各个顶点的度都相同，则这种无向图有__3__个（不考虑顶点的差异）。

( 2 分)6.下列有向图中，入度最大的顶点是___v2__；从v3到v2的最短简单路径有__v3v4v2__；包含所有顶点的简单路径有___v3v4v1v2____；有一简单回路是____v3v4v1(或v1v3v4,v4v1v3)___。

7.如果一棵完全二叉树有26个结点，从上到下、从左到右对它的结点进行编号，根结点为1号。

则该完全二叉树有__5__层；叶子结点有___13_个；第8号结点的双亲结点是__4__号；第11号结点的右孩子结点是__23__号。

四、综合计算简答题（共 6 小题，共27 分）1. 举出树结构的两个应用实例，并说明树的某个操作对应在实例中的意义。

( 5 分)答：家族族谱、文件系统、常见行政机构树结点的遍历相当于在文件系统中搜索特定的文件。

数据结构试题1总共：15题，共100.0分一、单选（共8小题，24.0分）1.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动______个元素。

（3分）A.8B.63.5C.63D.72.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在（）位置，(10)表明用10进数表示。

（3分）A.672(10)B.626(10)C.709(10)D.724(10)3.一个有序顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为________。

（3分）A.128B.127C.126D.2554.含5个结点（元素值均不相同）的二叉顺序搜索法查表，平均搜索长度为_______。

（3分）A.54B.42C.36D.655.在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。

若设失败结点i所在层次为I i，那么搜索失败到达失败所做的数据比较次数是__________。

（3.0分）A.I i+1 B.I i+2C.I i-1D.I i6.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均控查次数不超过1.5，则歼列存储空间应容纳________个表项。

（设搜索成功的平均搜索长度为s m=(1+1/(1-α))/2，其中α为装填因子）A.400B.526C.624D.6767.n个顶点的连通图至少有______条边。

（3.0分）A.n-1B.nC.n+1D.08.一个二叉树按顺序方式存储在一个一维数组中，如图01234567891011121314二、简答（共4小题，46.0分）1.如右所示的连通图，请画出：（1）以顶点①为根的深度优先生成树；（2）如果有关节点，请找出所有的关节点。

2.设有13个初始归并段，其长度分别为28，16，37，42，5，9，13，14，20，17，30，12，18。