山东07年专升本考试数据结构模拟试题.

作业题（一）一、单项选择题1. 从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2. 链表不具有的特点是（）A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（）。

For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1) B．O(n)C．O(n²) D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。

A．2 B．3C．4 D．65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。

A．98 B．100C．102 D．1066、判定一个栈s（最多元素为m0）为空的条件是（）。

A．s-〉top! =0 B．s-〉top= =0C．s-〉top! =m0 D．s-〉top= =m07、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。

A．（rear-front+m）%m B．rear-front+1C．rear-front-1 D． rear-front8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。

A．连接 B．求子串C．模式匹配 D．判子串9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。

(专升本)《数据结构》试题三套数据结构试题三套一、单选题1. 在二叉树的遍历过程中，如果先访问根节点，则得到的是：A. 先序遍历B. 中序遍历C. 后序遍历D. 层次遍历2. 下列数据结构中，不属于线性结构的是：A. 数组B. 链表C. 栈D. 队列3. 哪种数据结构可用于实现递归算法的运算过程？A. 数组B. 链表C. 栈D. 队列4. 在队列中，允许删除的一端称为：A. 队首B. 队尾C. 栈顶D. 栈底5. 下列哪种排序算法的时间复杂度最坏情况下也是O(nlogn)？A. 插入排序B. 冒泡排序C. 快速排序D. 选择排序二、填空题1. 拓扑排序是一种按照有向图的拓扑序列排列顶点的算法。

如果一个有向图存在环，则该图不可进行拓扑排序。

拓扑排序的时间复杂度为_______。

2. 假设有一个有n个元素的数组，要通过比较元素的大小来确定元素在数组中的位置，最坏情况下需要比较的次数为_______。

3. 假设有一个有n个元素的数组，按照从小到大的顺序进行插入排序。

已知数组在最坏情况下的逆序对数量为k，则进行插入排序的时间复杂度为_______。

4. 快速排序的时间复杂度取决于划分点的选择。

若每次总是选择数组的第一个元素作为划分点，则当数组已经有序时，快速排序的时间复杂度为_______。

5. 在哈希表中，冲突解决方法有很多种，其中比较常用的是_______和_______。

三、编程题1. 请编写一个函数，实现冒泡排序算法，并对一个整型数组进行排序。

2. 请编写一个函数，实现二分查找算法，并返回查找结果的索引位置。

3. 请编写一个函数，实现栈的逆序操作。

要求只能使用一个额外的栈空间。

4. 请编写一个函数，实现队列的逆序操作。

要求只能使用一个额外的栈空间。

5. 请编写一个函数，实现递归算法，计算斐波那契数列的第n项。

以上为《数据结构》试题三套，包括单选题、填空题和编程题。

通过这些试题，可以测试学生对数据结构相关知识的掌握程度，并培养其分析和解决问题的能力。

2007年山东省专升本计算机考试真题（含答案）2007年山东省专升本计算机考试真题一、填空题(20分，共10题，每题2分)1．二进制数100011011100转换成十六进制数是( )。

2．计算机处理数据时，CPU通过数据总线一次存取、加工和传输的数据称为（）。

3．未来的计算机将向巨型化、微型化、（）、智能化和多媒体化的方向发展。

4．Excel2003的编辑栏由名称框、（）和编辑区构成。

5．（）是Word中多个排版命令组合而成的集合。

6．在Word2003的“常用”工具栏中，（）工具按钮可以将字符和段落的格式复制到其他文本上。

7．Excel2003提供了（）和高级筛选两种筛选命令。

8．WindowsXP操作系统是一个（）的操作系统。

9．WWW的网络传输协议是（）。

10．用户计算机可以通过大型局域网、小型局域网、无线连接、电话拨号和（）等方式接入Intemet。

二、单项选择题(50分)1．计算机病毒不具有（）特性。

A．交互性B．破坏性C．潜伏性D．传染性2．计算机内处理汉字信息时所用的汉字代码是（）。

A．汉字字形码B．汉字输入码C．汉字机内码D．汉字交换码3．快捷方式就是一个扩展名为（）的文件。

A．dll B．Ink C．com D．exe4．在Word2003中不能创建表格的方法是( )。

A．单击“表格”菜单中的“插人”命令B．单击“常用”工具栏中的“插入表格”按钮C．单击“表格”菜单中的“绘制表格”命令D．单击“插人”菜单中的“表格”命令5．（）是微型计算机的输出设备。

A．显示器B．扫描仪C．键盘D．鼠标6．CAM的中文含义是（B ）。

A．计算机辅助设计B．计算机辅助制造C．计算机辅助工程D．计算机辅助教学7．多媒体具有多样性、交互性和( )A．可控性B．保密性C．通用性D．集成性8．常用的CD-RW光盘是（）的。

A．可擦写型B．只写一次C．追记型 D．只读9．显示器的分辨率不受（A ）的影响。

山东:07年专升本考试数据结构模拟试题1一、填空题:(每小题2分,共10分1. 设有数据结构(D,R,其中 D 是数据元素的有限集,R 是的有限集。

2. 深度为 k 的二叉树其结点数至多有个。

3. 栈是一种特殊的线性表,它允许在表的一端进行操作。

4. 通常象交通、道路问题的数学模型是一种称为的数据结构。

5. 哈希表是一种查找表,可以根据哈希函数直接获得。

二、单项选择题:(每小题2分,共10分对于下列各题,在备选答案中选出一个正确的,并将其编号填在“”位置上。

1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值,则采用存储方式最节省运算时间。

A. 单链表B. 双链表C. 单循环链表D. 顺序表2. 下列排序算法中,算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。

A. 直选择排序B. 冒泡排序C. 归并排序D. 堆排序3. 队列的操作原则是。

A. 先进后出B. 先进先出C. 只能进行插入D. 只能进行删除4. 在具有 n 个结点的二叉链表中,非空的链域个数为。

A. n-1B. nC. n+1D. 不确定5. 对具有 n 个元素的有序查找表采用折半查找算法查找一个键值,其最坏比较次数的数量级为。

A. O(log2nB. O(nC. O(nlog2nD. O(n2三、判断题:(每小题2分,共10分判断下列各题是否正确,若正确,在题后的括号内填“T”,否则填“F”。

1. 在栈为空的情况下不能作出栈处理,否则,将产生下溢出。

(2. 如果有向图 G=(V, E 的拓扑序列唯一,则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。

(3. 在大根堆中,必定满足每个结点的键值大于其左右子树中所有结点的键值。

(4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。

(5. 在索引顺序表中,对索引表既可采用顺序查找,也可采用二分查找。

(四、解答下列各题:(每题10分,共40分1. 已知线性表 L 采用带头结点的的单向循环链表表示,试给出它的存储结构类型描述及相应的示意图。

专升本⼗套-数据结构（试题及答案）数据结构试卷（⼀）⼀、单选题（每题2分,共20分）1.栈与队列得共同特点就是( )。

A、只允许在端点处插⼊与删除元素Ｂ、都就是先进后出C、都就是先进先出D、没有共同点2.⽤链接⽅式存储得队列,在进⾏插⼊运算时（）、A、仅修改头指针B、头、尾指针都要修改C、仅修改尾指针Ｄ、头、尾指针可能都要修改3.以下数据结构中哪⼀个就是⾮线性结构？( )Ａ、队列Ｂ、栈C、线性表Ｄ、⼆叉树4.设有⼀个⼆维数组A[m］［n］，假设Ａ［0］[０］存放位置在644（10）,A［２］［2］存放位置在６76（１0）,每个元素占⼀个空间，问A[3］[3](10)存放在什么位置？脚注(１0）表⽰⽤10进制表⽰。

A.6８8 B．６７8 C.6９2D．69６5.树最适合⽤来表⽰（)。

Ａ、有序数据元素B、⽆序数据元素C、元素之间具有分⽀层次关系得数据D、元素之间⽆联系得数据6.⼆叉树得第k层得结点数最多为( )、Ａ。

２ｋ—１ B、2K+1 C、2K-1 D、 2k-１7.若有１8个元素得有序表存放在⼀维数组A［19]中，第⼀个元素放A［１]中,现进⾏⼆分查找，则查找Ａ［3］得⽐较序列得下标依次为( )A、1,2,3 ??Ｂ、9，5，2，３C、9，５,3D、9,4，2，38.对ｎ个记录得⽂件进⾏快速排序，所需要得辅助存储空间⼤致为A、Ｏ(1）Ｂ、O（ｎ） C、 O（1og2n) D、 O(n２)9.对于线性表(7,34,5５，25,64，４6，20,10）进⾏散列存储时，若选⽤H（K）=K %9作为散列函数,则散列地址为1得元素有（）个，A。

1 B．2 C．3 D．410.设有6个结点得⽆向图,该图⾄少应有（)条边才能确保就是⼀个连通图。

A、5B、6C、7 Ｄ、8⼆、填空题（每空1分,共26分）1.通常从四个⽅⾯评价算法得质量：__＿＿＿_＿__、_________、______＿__与____＿_＿__.2.⼀个算法得时间复杂度为（n３＋ｎ2ｌog２n+14n）／n２,其数量级表⽰为________.3.假定⼀棵树得⼴义表表⽰为A(C，Ｄ（E,F，G），H(I，J）），则树中所含得结点数为__＿_______个，树得深度为________＿__，树得度为__＿______。

一、填空题：（每小题2分，共10分）1. 设有数据结构（D，R），其中D 是数据元素的有限集，R 是的有限集。

2. 深度为k 的二叉树其结点数至多有个。

3. 栈是一种特殊的线性表，它允许在表的一端进行操作。

4. 通常象交通、道路问题的数学模型是一种称为的数据结构。

5. 哈希表是一种查找表，可以根据哈希函数直接获得。

二、单项选择题：（每小题2分，共10分）对于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。

1. 若线性表最常用的操作是存取第i 个元素及其前驱元素的值，则采用存储方式最节省运算时间。

A. 单链表B. 双链表C. 单循环链表D. 顺序表2. 下列排序算法中，算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。

A. 直选择排序B. 冒泡排序C. 归并排序D. 堆排序3. 队列的操作原则是。

A. 先进后出B. 先进先出C. 只能进行插入D. 只能进行删除4. 在具有n 个结点的二叉链表中，非空的链域个数为。

A. n-1B. nC. n+1D. 不确定5. 对具有n 个元素的有序查找表采用折半查找算法查找一个键值，其最坏比较次数的数量级为。

A. O(log2n)B. O(n)C. O(nlog2n)D. O(n2)三、判断题：（每小题2分，共10分）判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。

1. 在栈为空的情况下不能作出栈处理，否则，将产生下溢出。

（）2. 如果有向图G=(V, E) 的拓扑序列唯一，则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。

（）3. 在大根堆中，必定满足每个结点的键值大于其左右子树中所有结点的键值。

（）4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。

（）5. 在索引顺序表中，对索引表既可采用顺序查找，也可采用二分查找。

（）四、解答下列各题：（每题10分，共40分）1. 已知线性表L 采用带头结点的的单向循环链表表示，试给出它的存储结构类型描述及相应的示意图。

专升本《数据结构》模拟题试卷专升本《数据结构》模拟题试卷一. （共75题,共150分）1. 数据的基本单位是（）。

（2分）A.数据元素B.记录C.数据对象D.数据项★检查答案标准答案：A2. （）是数据的不可分割的最小单位。

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

（2分）A.时间效率B.空间效率C.可读性D.健壮性★检查答案标准答案：B4. （）是限制了数据元素的内部结构仅为一个字符的线性表。

（2分）A.栈B.队列C.串D.数组★检查答案标准答案：B5. 串的长度是指串中所含（）的个数。

（2分）A.不同字符B.不同字母C.相同字符D.所有字符★检查答案标准答案：D（2采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。

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

（2分）A.顺序存取B.随机存取C.索引存取D.Hash存取★检查答案标准答案：B8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占字节，则2分）。

是（）（2mA.64B.32C.16D.8A★检查答案标准答案：分）2（深度为h的二叉树，第h层最多有（）个结点。

9.A.hB.2h-1C.2h-1D.2hC★检查答案标准答案：分）个结点的二叉树，其对应的二叉链表共有（）个非空链域。

2（10. mA.mB.m+1C.2mD.m-1B★检查答案标准答案：分）。

11. 下面叙述错误的是（）（2顺序表是借助物理单元相邻表示数据元素之间的逻辑关系A.对于空队列进行出队操作过程中发生下溢现象B.C.有向图的邻接矩阵一定是对称的D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的★检查答案标准答案：C12. 以下与数据的存储结构无关的术语是（）。

2007年山东省学分互认和专升本考试《数据结构》模拟试题(1)一、单项选择题(从下列各题四个备选答案中选出一个正确答案；每小题1分,共11分)1.数据的基本单位是____。

A.结点B.数据元素C.数据类型D.数据项2.下列算法suanfa1中语句"x=x*2；"的执行次数是____。

void suanfa1(int n){ int i,j,x=1；for(i=1；i<=n；i++)for(j=i；j<=n；j++)x=x*2；printf("%d",x)；}A.n(n-1)/2B.n(n+1)/2C.n2D.⎡nlog2n⎤3.当需要随机查找线性表的元素时,宜采用____作存储结构。

A.双向链表B.循环链表C.顺序表D.单链表4.若8行6列的数组以行序为主序顺序存储,基地址为2000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。

A.2086B.2032C.2068D.答案A,B,C都不对5.广义表(a,(b),c,(d,(e)))的表尾是____。

A.(d,(e))B.(d,(e))）C.(b),c,(d,(e))D.((b),c,(d,(e)))6.____是"Yu**Jia**Shan"的子串。

A.YuB."jia"C."**Shan"D."YuJiaShan"7.无向完全图的邻接矩阵是____矩阵。

A.对称B.上三角C.下三角D.稀疏8.有n(n>0)个结点的完全二叉树的深度是____。

A.⎡log2(n)+1⎤B.⎡log2(n)-1⎤C.⎣log2(n)-1⎦D.⎣log2(n)+1⎦9.与中缀表达式a-b/c+d等价的前缀表达式是____。

A.-a+/bcdB./-+bcdC.+-/bcdD.abcd-/+10.对有3600个记录的索引顺序表(分块表)进行查找,最理想的块长为____。

2007年10月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码2142)本试卷共8页，满分100分；考试时间150分钟。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．在数据结构中，从逻辑上可以把数据结构分成【】A．线性结构和非线性结构B．紧凑结构和非紧凑结构C．动态结构和静态结构D．内部结构和外部结构2．上面算法的时间复杂度为A．O(m2) B．O(n2)C．O(m×n) D．O(m+n)3．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为【】A．5 B．6C．7 D．94．设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p—llink 和p—rlink表示，则同样表示p指针所指向结点的表达式是【】5．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是【】A．110 B．108C．100 D．1206．设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是【】A．DCBA B．CDABC．DBAC D．DCAB7．在一个具有n个单元的顺序栈中，假定以地址低端(即0单元)作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为【】A．top++ B．top——C．top不变D．top=08．除根结点外。

树上每个结点【】A．可有任意多个孩子、一个双亲B．可有任意多个孩子、任意多个双亲C．可有一个孩子、任意多个双亲D．只有一个孩子、一个双亲9．题9图中树的度为【】A．2 B．3C．5 D．810．有4个顶点的无向完全图的边数为【】A．6 B．12C．16 D．2011．设图的邻接矩阵为，则该图为【】A．有向图B．无向图C．强连通图D．完全图12．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。

山东省专升本计算机考试真题2007年(总分：100.02，做题时间：120分钟)一、主观题（20分）（说明：此部分的答案直接填在试卷上）(总题数：10，分数：20.00)1.二进制数100011011100转换成十六进制数是 1。

（分数：2.00）填空项1:__________________ （正确答案：8DC）解析：2.计算机处理数据时，CPU通过数据总线一次存取、加工和传输的数据称为 1。

（分数：2.00）填空项1:__________________ （正确答案：字）解析：3.未来的计算机将向巨型化、微型化、 1、智能化和多媒体化的方向发展。

（分数：2.00）填空项1:__________________ （正确答案：网格化）解析：4.Excel 2000的编辑栏由名称框、 1和编辑区构成。

（分数：2.00）填空项1:__________________ （正确答案：工具按钮）解析：5. 1是Word中多个排版命令组合而成的集合。

（分数：2.00）填空项1:__________________ （正确答案：样式）解析：6.在Word 2000的“常用”工具栏中， 1工具按钮可以将字符和段落的格式复制到其他文本上。

（分数：2.00）填空项1:__________________ （正确答案：格式刷）解析：7.Excel 2000提供了 1和高级筛选两种筛选命令。

（分数：2.00）填空项1:__________________ （正确答案：自动筛选）解析：8.Windows 2000操作系统是一个 1的操作系统。

（分数：2.00）填空项1:__________________ （正确答案：单用户多任务）解析：9.WWW的网络传输协议是 1。

（分数：2.00）填空项1:__________________ （正确答案：HTTP协议）解析：10.用户计算机可以通过大型局域网、小型局域网、无线连接、电话拨号和 1等方式接入Internet。

2007年专升本考试计算机科学与技术专业综合第一部分（C程序设计）一、选择题(2’*25=50分)1. 以下叙述中正确的是______。

A、C程序中注释部分可以出现在程序中任意合适的地方B、花括号"{"和"}"只能作为函数体的定界符C、构成C程序的基本单位是函数，所有函数名都可以由用户命名D、分号是C语句之间的分隔符，不是语句的一部分2. 以下选项中可作为C语言合法整数的是______。

A、10110BB、0386C、0XffaD、x2a23. 以下不能定义为用户标识符的是______。

A、ScanfB、VoidC、_3com_D、int4. 有以下程序main(){ int a; char c=10;float f=100.0; double x;a=f/=c*=(x=6.5);printf("%d %d %3.1f %3.1f",a,c,f,x);}程序运行后的输出结果是______。

A、1 65 1 6.5B、1 65 1.5 6.5C、1 65 1.0 6.5D、2 65 1.5 6.55. 以下选项中非法的表达式是______。

A、0<=x<100B、i=j==0C、(char)(65+3)D、x+1=x+16. 有以下程序main(){ int a=1,b=2,m=0,n=0,k;k=(n=b>a)||(m=a<b);printf("%d,%d",k,m);}程序运行后的输出结果是______。

A、0,0B、0,1C、1,0D、1,17. 有定义语句：int x,y;。

若要通过scanf("%d,%d",&x,&y);语句使变量x得到数值11，变量y得到数值12，下面四组输入形式中，错误的是______。

A、11 12↙B、11,12↙C、11, 12↙D、11, ↙12↙8. 设有如下程序段int x=2007,y=2008;printf("%d",(x,y));则以下叙述中正确的是______。

《数据结构》模拟题2010年7月一、单选题（每空2分，共10分）1、队列的删除操作是在（）进行。

A．队首B．队尾C．队前D．对后2、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。

A．top++; B．top=0; C．top--; D．top=N;3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

A．51 B．23 C．53 D．744、在一棵二叉树中，第4层上的结点数最多为（）。

A．31 B．8 C.15 D．165、向堆中插入一个元素的时间复杂度为（）。

A．O(log2n) B．O(n) C．O(1) D．O(nlog2n)二、填空题（每空1分，共20分）1、数据的逻辑结构被分为____________、___________、____________和____________四种。

2、若对一棵二叉树的结点编号从1开始顺序编码，按顺序存储，把编号为1的结点存储到a[1]中，其余类推，则a[i]元素的左孩子元素为______，右孩子元素为_____，双亲元素(i>0)为________。

3、从一个栈删除元素时，首先取出，然后再前移一位。

4、后缀表达式“2 10 + 5 * 6 – 9 /”的值为。

5、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为______、______、______和______个。

6、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为________索引，若对应主表中的若干条记录，则称此索引为________索引。

8、对于二分查找所对应的判定树，它既是一棵_ ____，又是一棵_____ __ ___。

2007年山东省专升本考试数据结构真题一、判断题（10分。

本大题共10小题，每小题1分，在小题左面用√表示是，×表示否）1. 线性表的顺序存储结构是一种随机存储结构。

（）2. 一个栈的入栈序列是a, b, c, d, e，则dceab是一个不可能的输出序列。

（）3. 广义表(a, (a,b), d, e, ((i, j), k)) 的深度是2。

（）4. 树是一种重要的线性数据结构。

（）5. 按照二叉树的定义，具有三个结点的二叉树有5种。

（）6. 已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是求矩阵第i列非零元的个数。

（）7. 将递归算法转换为对应的非递归算法时，通常需要使用队列。

（）8. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。

（）9. 散列法存储的基本思想是由关键字的值决定数据的存储地址。

（）10. （101，88，46，70，34，39，45，58，66，10）是堆。

（）二、填空题（15分。

本大题共5小题，5个空，每个空3分，将正确答案填在空格处）。

1. 将下三角矩阵A[1..8, 1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7, 5]的地址为___________。

2. 若某二叉树有20个叶结点，有30个只有一个孩子的结点，则该二叉树的总结点数为___________。

3. 如果以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。

4. 在顺序存储的二叉树中，编号为i和编号为j的结点处在同一层的条件是___________。

5. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的结点时，___________次比较后查找成功。

三、（10分）已知关键字序列为{46，57，84，32，73，36，15，48，90，20}，要求：（1）构造一棵二叉排序树；（2）在等概率情况下，该二叉排序树查找成功的平均查找长度。

测试一下自己的水平一、判断题 (每小题1分，共15分)1.非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。

( )2.数组是一种没有插入与删除操作的线性结构。

( )3.稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。

( )4.空串与由空格组成的串没有区别。

( )5.将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。

( )6.深度为h的非空二叉树的第i层最多有2h-1 个结点。

( )7.完全二叉树就是满二叉树。

( )8.已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。

( )9.非空二叉排序树的任意一棵子树也是二叉排序树。

( )10.有向图是一种非线性结构。

( )11.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。

( )12.AOE 网是一种带权的无环连通图。

( )13.折半查找方法适用于按值有序的线性链表的查找。

( )14.哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。

( )15.选择排序过程中元素之间的比较次数与原始序列的状态无关。

( )二、单项选择题 (每小题2分，共20分)1.若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动_______个数据元素。

( )A.n-iB.n+iC.n-i-1D.n-i+12.在单链表中，已知q指的结点是q指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s 指的结点，则需执行________。

( )A.link(s)←link(p)，link(p)←sB.link(q)←s，link(s)←pC.link(p)←link(s)，link(s)←pD.link(p)←s，link(s)←q3.在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为:rlink(p)←q , llink(p)←llink(q) , llink←p, _________。

山东专升本统考公共课《计算机》模拟题及答案（一）模拟题一一、单选题1. 在Excel 2000表格单元格中出现一连串的“####”符号，则表示( )。

A 需调整单元格的宽度B 需重新输入数据C 需修改公式的内容D 需删去这些符号2. 在Excel 2000中，一个数据清单由三个部分组成( )。

A 区域、记录和字段B 公式、记录和数据库C 工作表、数据和工作簿D 数据、公式和函数3. 以下操作一定会应用于整个演示文稿所有幻灯片的是( )。

A 应用设计模板B 更换幻灯片版式C 修改幻灯片母版D 更改幻灯片配色方案4. 美国以外的国家的计算机域名通常在最后附上两个字母的( )。

A 国家代码B 服务代码C 用户代码D 机器名5. Word 2000不提供对( )进行正确性检查。

A 字符B 单词C 句子的时态D 汉语词汇6. 在Excel2000中,只能用于数值型数据的运算符是( )A ∧B ＋C －D ＞7. 在Excel2000中,如果要在某行上方插入多行,则需要选定( )。

A 插入的新行之下相邻的若干行B 该行C 该行的任意单元格D 无法插入多行8. 可以通过( )菜单来插入或删除行、列和单元格。

A 表格B 编辑C 视图D 格式9. 十六进制数5A.B的二进制表示是( )。

A 1011010.1011B 1101101.11C 1011011.111D 1010111.10110. 下列存储设备中，不属于外存的是( )。

A RAMB 优盘C 光盘D 硬盘11. 微机内部信息的传送是通过( )进行的。

A 总线B 芯片C CPUD 内存12. Windows 2000中，在不同的应用程序之间切换的快捷键是( )。

A Alt+TabB Ctrl+TabC Shift+TabD Ctrl+Break13. 下列说法正确的是( )。

A 画图程序可将图形存为位图文件B 画图程序只能绘制黑白图形C 画图程序中绘制的图形不能打印D 通过"开始"→"程序"→"画图"打开画图程序14. 在Windows 2000中，不可以通过“显示属性”对话框进行修改的是( )。