计算机应用基础数据结构部分试题及答案
1．选择题:
1.下面程序段的时间复杂度的量级为( )
for(i=1;i<=n;i++)
for (j=1;j<=i;j++)
for (k=1;k<=j;k++)
x=x+1;
A. O(1) 2.在数据结构中, 从逻辑上能够把数据结构分成( )
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
B.O(n)
C. O(n 2)
D.O(n 3) C.线性结构和非线性结构 D.内部结构和外部结构
3．数据结构的( ) 包括集合、 线性、 树形和图形结构四种基本类型。
A.存储结构 4．数据的( ) 包括查找、 插入、 删除、 更新和排序等。
A.存储结构
B.逻辑结构
C.基本运算
D.算法描述
5．数据的存储结构包括顺序、 链接、 散列和( ) 四种基本类型。
A.线性
B.数组
C.集合
D.索引
6．下面( ) 的时间复杂性最好, 即执行时间最短。
B.逻辑结构
C.基本运算
D.算法描述
A. O(n)
B.O(logn)
C. O(nlogn)
D.O(n 2)
7.下面程序段的时间复杂性的量级为( )
for(int i=0;i for (int j=0;j a[i][j]=i*j; A. O(m 2) 8．( A.正确性 B.O(n 2) C. O(m*n) D.O(m+n) ) 不是算法的基本特征。 B.长度有限 C.在规定时间内完成 D.确定性 9．一个栈的输入序列是 1, 2, 3, 4, 5, 则下列序列中( ) 是栈的输出序列。 A. 31245 10．在有 n 个结点的二叉链表中, 值为空的链域个数为( ) 。 A. n-1 B. 2n-1 C. n+1 D. 2n+1 B.41325 C.23415 D.14253 1-5 D C B C D 6-11 B C C C C 11．已知完全二叉树有 30个结点, 则整个二叉树有( ) 个度为 1的结点。 B. 1 C. 2 12．深度为 k 的完全二叉树至少有( ) 个结点。 A. 2k -1 2k-2 C. 2k-1 2k -2 13．深度为 k 的完全二叉树至多有( ) 个结点。 A. 2k -1 2k-2 C. 2k-1 2k -2 A. 0 D. 不确定 B. D. B. D. 14．对一组记录( 54, 38, 96, 23, 15, 72, 60, 45, 83) 进行直接插入排序, 当把第 7个记录 60插入到有序表时, 为寻找插入位置需比较( ) 次。 A. 1 B. 2 C. 3 D. 4 15．折半查找有序表( 6, 15, 30, 37, 65, 68, 70, 72, 89, 99) , 若查找元素 37, 需依次与表中元素( ) 进行比较。 A. 65, 15, 37 B. 68, 30, 37 C. 65, 15, 30 16．一个长度为 n的顺序存储的线性表中, 向第 i个元素(1≤i≤n+1)位置插入一 D. 65, 15, 30, 37 个新元素时, 需要从后面向前依次后移( ) 个元素。 C. n-i-1 ) 不是完全二叉树。 A. n-i 17．如图所示的 4棵二叉树中, ( B. n-i+1 D. I ( A) (B) (C) (D) 18．对于长度为 18的顺序存储的有序表, 若采用折半查找, 则查找第 15个元素的查找长度为( A. 3 ) 。 B. 4 C.5 D.6 19．设有 10000个无序元素, 希望用最快的速度挑选出其中前 10个最大元素, 最好选用( A.堆排序 20．计算机算法指的是( ) 。 A.计算方法 B.排序方法 ) 排序法。 B.快速排序 C.起泡排序 D.插入排序 D.调度方法 C.解决问题的有序序列 11-15 B C A C D 16-20 B A B A C 21．一个栈的入栈序列 1, 2, 3, 4, 则它的不可能的输出序列是( A. 1, 2, 3, 4 B. 4, 3, 2, 1 C. 1, 3, 4, 2 D. 4, 1, 2, 3 22．对于任何一棵二叉树, 如果其终端结点数为 N0, 度为 2的结点数为 N2, 则 ) 。 N0=( ) 。 A. N2-1 B. N2+1 C. N2 D. N2-2 23．线性表是( ) A.一个有限序列, 能够为空 C.一个无限序列, 能够为空 B.一个有限序列, 不能为空 D.一个无限序列, 不能为空 24．在一个长度为 n的线性表中, 删除值为 x的元素时需要比较元素和移动元素的总次数为( ) A.( n+1) /2 25．在一个顺序表的表尾插入一个元素的时间复杂度的量级为( ) A. O(n) C. O(n2) B.n/2 C. n D.n+1 B.O(1) D.O(logn) 26．设单链表中指针 p指向结点 ai,若要删除 ai之后的结点( 若存在) , 则需修改指针的操作为( ) 。 A. p->next= p->next->next B. p=p->next C. p=p->next->next D. next=p 27．设单链表中指针 p指向结点 a i,指针 f指向将要插入的新结点 x, 则当 x插在链表中两个数据元素 a i和 a i+1之间时, 只要先修改( ) 后修改( ) 即可。 A. p->next= f C. p->next=f->next E. f->next=null B. p->next= p->next->next D. f->next= p->next F. f->next=p 28．设单链表中指针 p 指向结点 a i ,指针 f 指向将要插入的新结点 x, 则在链表中 最后一个结点 a n 之后插入时, 只要先修改( ) 后修改( ) 即可。 A. f->next= p C. p->next=f E. f =null B. f->next= p->next D. p->next= f->next 29．在一个单链表中, 若要在 p 所指向的结点之后插入一个新结点, 则需要相继 修改( ) 个指针域的值。 A. 1 B. 2 C. 3 D.4 30．在一个单链表中, 若要在 p 所指向的结点之前插入一个新结点, 则此算法的 时间复杂性的量级为( ) A. O(n) B.O(n/2) C. O(1) D.O(n 1/2) 21-25 D B A C B 26-30 A (D.A) (B.C) B A 31．不带头结点的单链表 L 为空的判定条件是( ) 。 A. L= = NULL C. L->next = = L B. L->next = = NULL D. L! = NULL 32．带头结点的单链表 L 为空的判定条件是( ) 。 A. L= = NULL C. L->next = = L B. L->next = = NULL D. L! = NULL 33．在一个带有头结点的双向循环链表中, 若要在 p 所指向的结点之前插入一个 新结点, 则需要相继修改( ) 个指针域的值。 A. 2 B. 3 C. 4 D.6 34．在一个带有头结点的双向循环链表中, 若要在 p 所指向的结点之后插入一个 q 指针所指向的结点, 则需要对 q->next 赋值为( ) A. p->prior B. p->next C. p->next->next D. p->prior ->prior 35．对一个具有 n 个元素的线性表, 建立其单链表的时间复杂度为( ) A. O(n) C. O(n 2) B.O(1) D.O(logn) 36．线性表采用链式存储时, 其地址 ( ) A.必须是连续的 B.一定是不连续的 C.部分地址必须是连续的 D.连续与否均能够 37．假定利用数组 a[N]顺序存储一个栈, 用 top 表示栈顶指针, top= =-1表示栈 空, 并已知栈未满, 当元素 x 进栈时所执行的操作为( ) A. a[--top]=x B. a[top--]=x C. a[++top]=x D .a[top++]=x 38．若已知一个栈的入栈序列是 1, 2, 3, …..n , 其输出序列为 p1, p2, p3,….. pn , 若 p1=n, 则 pi 为( ) A. i 39．判定一个栈 S( 最多元素为 m 0) 为空的条件是( ) A. S. top!=0 B. S. top= =0 C. S. top!=m 0 D .S. top= =m 0 40．判定一个栈 S( 最多元素为 m 0) 为满的条件是( ) A .S. top!=0 B. S. top= =0 C. S. top!=m 0-1 D .S. top= =m 0-1 B.n-i C. n-i+1 D.不确定 31-35 A B C B A 36-40 D C C B D 41．一个队列的入队序列是 1, 2, 3, 4, 则队列的输出序列是( ) A.4, 3, 2, 1 B. 1, 2, 3, 4 C. 1, 4, 3, 2 D .3, 2, 4, 1 42．从一个顺序循环队列中删除元素时, 首先需要( ) A.前移队首指针 B.后移队首指针 C.取出队首指针所指位置上的元素 D .取出队尾指针所指位置上的元素43．假定一个顺序循环队列的队首和队尾指针分别用 front和 rear表示, 则判断队列空的条件为( ) A.front+1= =rear B.rear+1= =front C. front= =0 D . front= =rear 44．假定一个顺序循环队列存储于数组 a[N]中, 其队首和队尾指针分别用 front 和 rear表示, 则判断队列满的条件为( ) A.( rear-1) %N= =front C.( front-1) %N= =rear B.( rear+1) %N= =front D .( front+1) %N= =rear 45．树中所有结点的度等于所有结点数加( ) A.0 B.1 C.-1 D.2 46．在一棵树中, 每个结点最多有( ) 个前驱结点。 A.0 B.1 C.2 D.任意多个 47．在一棵度为 3的树中, 度为 3的结点数为 2个, 度为 2的结点数为 1个, 度为 1的结点点数为 2个, 则度为 0的结点数为( ) 个。 A.3 B.4 C.5 D.6 48．在一棵二叉树上第 5层的结点数最多为( ) A.16 B.15 C.8 D.32 49．在一棵具有 n个结点的二叉树的第 i层上, 最多具有( ) 个结点。 B. 2i+1 C. 2i-1 D. 2n 50．一颗具有 35个结点的完全二叉树的深度为( ) A.2i A.6 B.7 C.5 D.8 41-45 B B D B C 46-50 B D A C A 51．在一棵完全二叉树中, 若编号为 i的结点存在右孩子, 则右孩子结点的编号为( ) A.2i B.2i-1 C.2i+1 D.2i+2 52．设高度为 h的二叉树上只有度为 0和度为 2的结点, 则此类二叉树中所包含的结点数至少为( ) A.2h B.2h-1 C.2h+1 D.h+1 53．按照二叉树的定义, 具有 3个结点的二叉树有( ) 种状态。 A.5 B.4 C.3 D.30 54．若查找每个元素的概率相等, 则在长度为 n的顺序表上查找任意元素的平均查找长度为( ) A.n B.n+1 C.( n-1) /2 D.( n+1) /2 55．顺序查找法适合于存储结构为( ) 的线性表。 A.散列存储C.压缩存储 B.顺序存储或链接存储D.索引存储 56．对于顺序存储的有序表( 5, 12, 20, 26, 37, 42, 46, 50, 64) , 若采用折半查找, 则查找元素 26的查找长度( ) A.2 B.3 C.4 D.5 57．对线性表进行折半查找时, 要求线性表必须( ) A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储, 且结点按关键字有序排序 D.以链接方式存储, 且结点按关键字有序排序 58．采用折半查找方法查找长度为 n 的线性表时, 每个元素的平均查找长度为( ) A. O(n 2) 59．在对 n 个元素进行直接插入排序的过程中, 共需要进行( ) 趟。 A .n 60．对 n 个元素进行直接插入排序时间复杂度为( ) A. O(1) C. O(n) D. O(nlog2n) B. O(n 2) B. O(nlogn) C. O(n) D. O(logn) B.n+1 C.n-1 D.2n 51-55 C B A D B 56-60 C C D C B 61．在对 n 个元素进行快速排序的过程中, 最好情况下需要进行( ) 趟。 A. n B. n/2 C. logn D. 2n 62．在对 n 个元素进行冒泡排序的过程中, 至少需要( ) 趟完成。 A. 1 B. n C. n-1 D. n/2 63．在对 n 个元素进行快速排序的过程中, 平均情况下的时间复杂度为( ) A. O(1) B. O(logn) D. O(nlogn) C. O(n 2) 64．排序方法中, 从未排序序列中依次取出元素与已排序序列( 初始时为空) 中 的元素进行比较, 将其放入已排序序列的正确位置上的方法, 称为( ) A.插入排序 B.起泡排序 C.希尔排序 D.选择排序 65．用某种排序方法对线性表( 25, 84, 21, 47, 15, 27, 68, 35, 20) 进行排 序时, 元素序列的变化情况如下: ( 1) 25, 84, 21, 47, 15, 27, 68, 35, 20 ( 2) 20, 15, 21, 25, 47, 27, 68, 35, 84 ( 3) 15, 20, 21, 25, 35, 27, 47, 68, 84 ( 4) 15, 20, 21, 25, 27, 35, 47, 68, 84 则采用的排序方法是( ) 。 A.选择排序 B.希尔排序 C.插入排序 D.快速排序 66．对下列四个序列进行快速排序, 各以第一个元素为基准进行第一次划分, 则 在该次划分过程中需要移动元素次数最多的序列为( ) 。 A. 1, 3, 5, 7, 9 C. 5, 3, 1, 7, 9 B. 5, 7, 9, 1, 3 D. 9, 7, 5, 3, 1 67．若对 n 个元素进行简单选择排序, 则进行任一趟排序的过程中, 为寻找最小 值元素所需要的时间复杂度为( ) A. O(1) B. O(logn) C. O(n) D. O(n 2) 68．若对 n 个元素进行堆排序, 则在由初始堆进行每趟排序的过程中, 共需要进 行( ) 次筛运算。 A. n+1 B. n/2 C. n D. n-1 69．排序方法中, 从未排序序列中挑选元素, 并将其依次放入已排序序列( 初始 时为空) 的一段的方法, 称为( ) 。 A. 希尔排序 B.起泡排序 C.插入排序 D.选择排序 70．一组记录的关键字为( 45, 80, 55, 40, 42, 85) , 则利用堆排序的方法建 数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n） 计算机基础综合知识试题及答案 1．微机中1K字节表示的二进制位数是( )。D A、1000 B、8x1000 C、1024 D、8x1024 2．计算机硬件能直接识别和执行的只有( )。D A、高级语言 B、符号语言 C、汇编语言 D、机器语言 3．用于保存计算机输入输出数据的材料及其制品称为( )。A A、输入输出媒体 B、输入输出通道 C、输入输出接口 D、输入输出端口 4．计算机中，一个浮点数由两部分组成，它们是( )。A A、阶码和尾数 B、基数和尾数 C、阶码和基数 D、整数和小数 5．下面是关于解释程序和编译程序的论述，其中正确的一条是( )。C A、编译程序和解释程序均能产生目标程序 B、编译程序和解释程序均不能产生目标程序 C、编译程序能产生目标程序而解释程序则不能 D、编译程序不能产生目标程序而解释程序能 6．硬盘工作时应特别注意避免( )。B A、噪声 B、震动 C、潮湿 D、日光 7．在Word中，打开文档的作用是( )。C A、将指定的文档从内存中读入，并显示出来 B、为指定的文档打开一个空白窗口 C、将指定的文档从外存中读入，并显示出来 D、显示并打印指定文档的内容 8．在Word主窗口的右上角、可以同时显示的按钮是( )。C A、最小化、还原和最大化 B、还原、最大化和关闭 C、最小化、还原和关闭 D、还原和最大化 9．在Word的编辑状态，设置了一个由多个行和列组成的空表格，将插入点定在某个单元格内，用鼠标单击"表格"命令菜单中的"选定行"命令，再用鼠标单击"表格"命令菜单中的"选定列"命令，则表格中被选择的部分是( )。D A、插入点所在的行 B、插入点所在的列 C、一个单元格 D、整个表格 10．当前活动窗口是文档d1.Doc的窗口，单击该窗口的"最小化"按钮后( )。A A、不显示d1.doc文档内容，但d1.doc文档并未关闭 B、该窗口和d1.doc文档都被关闭 C、d1.doc文档未关闭，且继续显示其内容 D、关闭了d1.doc文档但该窗口并未关闭 11．如果想在Word主窗口中显示常用工具按钮，应当使用的菜单是( )。B A、"工具"菜单 B、"视图"菜单 C、"格式"菜单 D、"窗口"菜单 12．在Word的编辑状态，设置了标尺，可以同时显示水平标尺和垂直标尺的视图方式是( )。B A、普通视图 B、页面视图 C、大纲视图 D、全屏显示方式 13．在Excel中，选取一行单元格的方法是( )。A A、单击该行行号 B、单击该行的任一单元格 C、在名称框输入该行行号 D、单击该行的任一单元格，并选"编辑"菜单的"行"命令 14．当启动Excel97后，Excel将自动打开一个名为( )的工作簿。C A、文档1 B、Sheet1 C、Book1 D、EXCEL1 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 P175: 5. 设有关系模式R(A,B,C,D)，函数依赖F={A→C, C→A, B→AC, D→AC，BD→A } 1)求R的所有候选键。 2)求出F的最小函数依赖集Fmin。 3)根据函数依赖关系，确定关系模式R属于第几范式。 4)将R分解为3NF，并保持无损连接性和函数依赖性。 答：1）属性分类为: L类:B,D ; LR类:A,C; R类:无; N类:无 因为（BD）+=ABCD ,所以BD是唯一候选键. 2） ●函数依赖F={A→C, C→A, B→AC, D→AC, BD→A }右部分解为单属性为 F={A→C, C→A, B→A, B→C, D→A, D→C, BD→A } ●因为B+=ABC,所欲BD→A，D为左部多余的属性.将D去掉，则 F={A→C, C→A, B→A, B→C, D→A, D→C } ●冗余函数依赖: 因为B+=ABC,所以B→A多余,去掉. 因为D+=ACD,所以D→A多余,去掉. 所以Fmin={A→C, C→A, B→C, D→C } 4)根据算法4.6，以及Fmin，F中没有X→Y，XY=R的函数依赖，也没有属性在F的函数依赖中左右都无关。所以将Fmin中的各个函数依赖单独构成一个关系模式， 对于Fmin中每一个函数依赖： A→C：表中数据不改变； C→A：将A中所有b给为a1； 表中没有都是a的行，所以不是无损连接的。 因此根据算法 4.7，将候选键作为一个关系模式加入到ρ中，所以结果为ρ={AC,BC,DC，BD} 6.设有关系模式R(A,B,C,D)，函数依赖F={A→C, C→A, B→AC, D→AC } 1)求（AD）+，B+。 2)求出R 的所有候选键。 3)求出F的最小函数依赖集Fmin。 4)根据函数依赖关系，确定关系模式R属于第几范式。 5)将R分解为3NF，并保持无损连接性和函数依赖性 6)略 答： 一、单项选择题（1～50小题，每题1.5分，共75分） 1.若在Excel的同一单元格中输入的文本有两个段落，则在第一段落输完后应使用（ C ）键。 (A)Enter (B)Ctrl+Enter (C)Alt+Enter (D)Shift+Enter 2.在下列存储器中，访问速度最快的是（ D ）。 (A)硬盘存储器 (B)软盘存储器 (C)磁带存储器 (D)半导体RAM(内存储器) 3.具有多媒体功能的微机系统，常用CD-ROM作为外存储器，它是（ B ）。 (A)只读软盘存储器 (B)只读光盘存储器 (C)可读写的光盘存储器 (D)可读写的硬盘存储器 4.在微机中，存储容量为5MB，指的是（ D ）。 (A)5×lO00×1000个字节 (B)5×1000×1024个字节 (C)5×1024×1000个字节 (D)5×1024×1024个字节 5.目前计算机的应用领域可大致分为三个方面，指出下列答案中正确的是（ C ）。 (A)计算机辅助教学专家系统人工智能 (B)工程计算数据结构文字处理 (C)实时控制科学计算数据处理 (D)数值处理人工智能操作系统 6.算法的基本结构中不包括（ A ）。 (A)逻辑结构 (B)选择结构 (C)循环结构 (D)顺序结构 7.对同一幅照片采用以下格式存储时，占用存储空间最大的格式是（C）。 (A).JPG (B).TIF (C).BMP (D).GIF 8.可被计算机直接执行的程序由（A）语言编写的程序。 (A)机器 (B)汇编 (C)高级 (D)网络 9.关系数据库中的数据逻辑结构是（D）。 (A)层次结构 (B)树形结构 (C)网状结构 (D)二维表格 10.在Internet上用于收发电子邮件的协议是（C）。 (A)TCP/IP (B)IPX/SPX (C)POP3/SMTP (D)NetBEUI 11.函数重载是指（ A ）。 (A)两个或两个以上的函数取相同的函数名，但形参的个数或类型不同 (B)两个以上的函数取相同的名字和具有相同的参数个数，但形参的类型可以不同 (C)两个以上的函数名字不同，但形参的个数或类型相同 (D)两个以上的函数取相同的函数名，并且函数的返回类型相同 12.在下面循环语句中循环体执行的次数为（ C ）。 int i=0,s=0; while(s<20) {i++; s+=i;} (A) 4 (B) 5 (C) 6 (D) 7 13.假定变量a和pa定义为“double a[10], *pa=a;”，要将12.35赋值给a中的下标为5的元素，不正确的语句是（ D ）。 （A）pa[5]=12.35 (B) a[5]=12.35 (C) *(pa+5)=12.35 (D) *(a[0]+5)=12.35 14.关于封装，下列说法中不正确的是（ D ）。 (A) 通过封装，对象的全部属性和操作结合在一起，形成一个整体 (B) 通过封装，一个对象的实现细节被尽可能地隐藏起来（不可见） (C) 通过封装，每个对象都成为相对独立的实体 (D) 通过封装，对象的属性都是不可见的 15. 假定一个类AB只含有一个整型数据成员a，用户为该类定义的带参构造函数可以为( C )。 (A) AB() {} (B) AB(): a(0){} (C) AB(int aa=0) {a=aa;} (D) AB(int aa) {} 16. 下面程序定义了一个类，关于该类说法正确的是( B ) abstract class abstractClass{ …… } (A) 该类能调用new abstractClass()，方法实例化为一个对象 (B) 该类不能被继承 (C) 该类的方法都不能被重载 (D) 以上说法都不对 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 计算机基础综合试题 一、选择题（１6×３＝４8分） １、微型计算机的性能主要取决于。 Ａ、内存Ｂ、中央处理器Ｃ、硬盘Ｄ、主板 ２、在一个无符号二进制整数的右边填上一个０，形成的数是原数的。 Ａ、１倍Ｂ、２倍Ｃ、３倍Ｄ、４倍 ３、目前微软公司提供的最广泛的电子邮件收发软件是。 Ａ、Internet Explorer Ｂ、Windows 98 Ｃ、Outlook Express Ｄ、Fox Mail ４、用ＭＩＰＳ来衡量的计算机性能指标是。 Ａ、处理能力Ｂ、存储容量Ｃ、可靠性Ｄ、运算速度 ５、若存储器芯片共有２４根地址线的引脚，则该存储器芯片的最大存储容量为。 Ａ、512KB Ｂ、1MB Ｃ、8MB Ｄ、16MB ６、微机开电源后开始执行的指令是放在。 Ａ、硬盘Ｂ、ＣＰＵＣ、ＲＯＭＤ、ＲＡＭ ７、关于“网上邻居”叙述不正确的是。 A、网上邻居是Windows98的新增功能 B、通过网上邻居可以浏览网上的计算机 C、通过网上邻居可以浏览网上打印机 D、通过网上邻居可以浏览多个网络的计算机８、如果有４＊７＝３４，则该数为进制。 Ａ、２Ｂ、８Ｃ、１０Ｄ、１６ ９、实现汉字表示的方法有两种，它们是。 Ａ、点阵式和矢量式Ｂ、点阵式和网络式Ｃ、向量式和网络式Ｄ、向量式和矢量式 １０、Internet是国际互联网，下面不是它所提供的服务。 Ａ、Ｅ－mail Ｂ、远程登录Ｃ、故障诊断Ｄ、信息查询 １１、CPU芯片中使用流水线技术的目的是。 A、扩充功能 B、降低资源消耗 C、提高运行速度 D、减少功耗 １２、通常说的0.28反映了显示器的，它是显示性能的主要技术指标之一。 A、刷新率 B、灰度率 C、分辨率 D、点距 １３、IP协议是之间的协议。 A、在Internet中任何计算机网络 B、在Internet中任何计算机 C、Internet和Intranet D、Internet和非Intranet １４、计算机网络系统安全级别从低到高共有７级，其中Ｗindows NＴ技术达到。 Ａ、Ｄ１级Ｂ、Ｃ１级Ｃ、Ｃ２级Ｄ、Ａ级 １５、多媒体计算机是指。 Ａ、能与家用电器连接使用的计算机Ｂ、能处理多种媒体信息的计算机 Ｃ、连接有多种外部设备的计算机Ｄ、能玩游戏的计算机 １6、下列属于QBASIC合法常量的是 A、INT(3.8) B、E+2 C、3D-2 D、2+5 二、填空题：（１6×２＝3２分） １、Internet的域名和ＩＰ地址之间的关系是。 ２、计算机网络的主要功能是和。 ３、多媒体技术的特征是指其具有数字化、集成性、实时性和。 ４、计算机病毒是一个在计算机内部或系统之间进行自我繁殖和扩散的。５、在网络体系结构中，ＯＳＩ的７层协议：①数据链路层②网络层③表达层④应用层⑤会 单元练习1 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 （4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 （6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。（9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。 （13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。 （14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。 （18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O （nlog2n）。 （19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 数据结构期末考试题及标准答案 ————————————————————————————————作者：————————————————————————————————日期： 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 期末试卷1 一、简答题（每题5分，共10分） 1. 信息社会需要什么样的人才？ 2. 计算机中的信息为何采用二进制系统？ 二、填空题（每题1分，共20分） 请将正确的答案填在横线上。 1. 电子数字计算机能够自动地按照人们的意图进行工作的最基本思想是程序存储，这个思想是提出的。 2. 微型计算机的主要技术指标是、运算速度、内存容量、可靠性和可用性等五项指标。 3. 计算机先后经历了以电子管、、集成电路、大规模和超大规模集成电路为主要元器件的时代。 4. (159)10 = ( ) 2 = ( )8 = ( )16。 5. 微型计算机系统按传输信息的类型分为数据、控制和地址三种总线，其中总线决定了CPU的最大寻址能力。 6. 在微机中，字符的比较就是对它们的码值进行比较。 7. 在计算机系统中，1个西文字符由个字节组成。 8. 操作系统的工作界面有和两种。 9. 操作系统的功能主要有、内存分配和管理、外设的控制和管理、文件管理、作业管理和控制五项。 10. 在计算机中表示数时，小数点固定的数称为，小数点不固定的数称 为。 11. 按内存中同时运行程序的数目，可以将批处理系统分为和两类。 12. 在Windows中，按键可以将整个屏幕内容复制到剪贴板，按键可以将当前使用程序窗口复制到剪贴板。 13. 剪贴板是内存中的一个缓冲区，通过剪切或复制的方法放到剪贴板上，然后再将剪贴板上的内容通过方法放到另一个使用程序文档中。 14. 在幻灯片上如果需要一个按钮，当放映幻灯片时单击此按钮能跳转到另外一张幻灯片，则必须为此按钮设置。 15. 在Intranet中通常采用技术以保护企业内部的信息安全。 16. 计算机病毒是指“编制或在计算机程序中插入的破坏计算机功能或毁坏数据、影响计算机使用、并能自我复制”的一组。 17. 如果采用拨号方式接入Internet，用户所需要的硬件设备有：一台计算机、一条电话线、一根RS232电缆和一台。 18. 在计算机网络中，使用域名方式访问Internet上的某台计算机时，需要通过转换成IP地址才能被Internet识别。 19. 将远程主机上的文件传送到本地计算机上称为文件。 数据结构（本科）试卷7 一、选择题（每小题1分，共10分） 1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是： A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 3.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为 对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址 5.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. –1 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长 度为（）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（）。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 9.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10.当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。 A. 较慢 B.较快 C. 相同 二、填空题（每小题1分，共10分） 1.二维数组是一种非线性结构，其中的每一个数组元素最多有____2___个直接前驱（或直 接后继）。 2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中， A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_ 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 普通高校职业教育单独招生考试 《计算机》模拟试题（卷） 考号班级成绩 一、单选择题：（每题1分，共20分） 1、在Ｗindows XP 桌面上不能删除的图标是（） A) 回收站B) 我的电脑C) 资源管理器D) 工具箱 2、计算机应用广泛，而其应用最广泛的领域是（） A)科学与工程计算B)数据处理与办公自动化 C)辅助设计与辅助制造D)信息采集与过程控制 3、下列叙述中错误的是（） A)计算机要经常使用，不要长期闲置不用 B)为了延长计算机的寿命，应避免频繁开关计算机 C)在计算机附近应避免磁场干扰 D)计算机用几小时后，应关机一会儿再用 4、在WORD中，选择“绘图”工具栏中的“插入艺术字”对话框，共有（）种式样。 A). 5B). 15 C). 25D). 30 5、下列叙述正确的是（） A)任何存储器都有记忆，其中的主存不会丢失 B)操作系统的功能之一是提高计算机的运行速度 C)硬盘装在主机箱内，因此硬盘属于主存 D)磁盘驱动器和磁盘属于外设 6、下列设备中，既能向主机输入数据又能接收主机输出数据的设备是（） A)CD-ROMB)显示器C)U盘D)光笔 7、CAE表示计算机（）。A) 辅助模拟B)辅助设计C) 辅助制造D) 辅助教学 8. 下列4种设备中，属于计算机输入设备的是___________。 A．UPS B．投影仪C．绘图仪D．鼠标器 9. 下列术语中，属于显示器性能指标的是___________。 A．速度B．分辨率c．可靠性D．精度 10. 具有多媒体功能的微型计算机系统中，常用的CD-ROM是___________。 A．只读型大容量软盘B．只读型光盘C．只读型硬盘D．半导体只读存储器 11. Windows音频工具“录音机”录制的声音被保存的文件夹扩展名为。 A、MP3 B、MID C、AVI D、WAV 12. 在Windows中，“写字板”是一种。 A、字处理软件 B、画图工具 C、网页编辑器 D、造字程序 13.在Windows中，能弹出对话框的操作是。 A、选择了带“…”的菜单项 B、选择了带向右三角形箭头的菜单项 C、选择了颜色变灰的菜单项 D、运行了与对话框对应的应用程序 14. 在Word 文档的每一页都需要出现同一公司的徽标，应将公司徽标放到（） A.图形中 B.页眉／页脚中 C.文本框中 D.图文框中 15. 在Word 中，不属于段落格式设置的是( ) A.首行缩进 B.居中 C.两端对齐 D.字符间距 16. 十进制数269转换成十六进制数为（）。 A、10E B. 10D C. 10C D. 10B 17. 选定Word表格的某一列后，再按Del键，结果是( ) A.该列被删除，表格减少一列 B.该列的内容被删除 1. 下面程序段的执行次数为（ A ） for(i=0;i＜n-1;i++) for(j=n;j＞i;j--) state; A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2) 2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （ B ）A. 110 B .108 C. 100 D. 120 3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde 4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前 队列中的元素个数是（ D ） A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front 5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head D. head!=NULL 6．在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行（ B） A. s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p; 7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较多少个结点（ D ）A. n B .n2 C. (n-1)2 D. (n+1)28．从一个栈顶指针为HS 的链栈中删除一个结点时，用x保存被删结点的值，则执行( D )A. x=HS;HS=HS-next;B .x=HS-data;C. HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表，其特殊性体现在( B ) A. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字 符11．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的 范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存 储时下列哪一元素的起始地址相同( B ) A. M[2][4] B .M[3][4] C. M[3][5] D. M[4][4] 12. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10， 从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为 ( C )A. SA+144 B .SA+180 C. SA+222 D. SA+225数据结构考试试题及答案
计算机基础综合知识试题及答案
数据结构课后习题答案
数据结构DB课后题部分答案
计算机综合试题
数据结构课后习题及答案
2017年数据结构期末考试题及答案A
计算机基础综合试题及答案
《数据结构》课后参考答案
数据结构作业及答案范文
数据结构期末考试题及标准答案
计算机基础综合试卷_教师_试题_阳飞试卷一_(1)
数据结构试题(附有答案)
《数据结构》期末考试题及答案
高考单招计算机基础综合试题(附详细答案)
武汉大学数据结构考试题(附答案)
相关主题
文本预览