厦门理工学院数据结构期末考试试题

2022年厦门理工学院数据科学与大数据技术专业《计算机网络》科目期末试卷B（有答案）一、选择题1、在OSl参考模型中，自下而上第一个提供端到端服务的是（）。

A.数据链路层B.传输层C.会话层D.应用层2、局域网和广域网之间的差异是（）。

A.所使用的传输介质不同B.所覆盖的范围不同C.所使用的协议不同D.B和C3、主机地址172.16.2.160属于下面哪个子网？（）A.172.16.2.64/26B.172.16.2.96/26C.172.16.2.128/26D.172.16.2.192/264、下列IP地址中，只能作为IP分组的源IP地址但不能作为目的IP地址的是（）。

A.0.0.0.0B.127.0.0.1C.200.10.10.3D.255.255.255.2555、以太网帧的最小长度是（）。

A.32B.64C.128D.2566、为了纠正2比特的错误，编码的海明距应该为（）。

A.2B.3C.4D.57、如果用户程序使用UDP进行数据传输，那么（）协议必须承担可靠性方面的全部工作。

A.数据链路层B.网络层C.传输层D.应用层8、主机甲和主机乙新建一个TCP连接，甲的拥塞控制初始阀值为32KB，甲向乙始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙为该连接分配16KB接收缓存，并对每个数据段进行确认，忽略段传输延迟。

若乙收到的数据全部存入缓存，本被取走，则甲从连接建立成功时刻起，未发送超时的情况下，经过4个RTT后，甲的发送窗口是（）。

A.1KBB.8KBC.16KBD.32KB9、主机甲和主机乙已建立了TCP连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认段。

若甲在t时刻发生超时拥塞窗口为8KB，则从t时刻起，不再发生超时的情况下，经过10个RTT后，甲的发送窗口是（）。

A.10KBB.12KBC.14KBD.15KB10、下列说法错误的是（）A.P2P是网络结点之间采取对等的方式直接交换信息的工作模式B.客户机是面向任务的，服务器是面向用户的C.客户机通常位于前端，服务器通常位于后端D.客户机和服务器之间是通过网络来实现协同计算任务的11、下面有关DNS的说法中正确的是（）。

数据结构c语言期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的区别在于（）。

A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一关系D. 结构中元素之间是否有一对多关系答案：C2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 存储密度高B. 存储密度低C. 插入和删除操作快D. 存储空间可以动态分配答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。

A. i-1B. n-iC. n-i+1D. n-i-1答案：B4. 栈的运算遵循（）原则。

A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：C5. 在二叉树的前序遍历中，访问顺序为（）。

A. 根-左-右B. 左-根-右C. 左-右-根D. 右-左-根答案：A6. 哈希表的冲突解决方法中，链地址法是（）。

A. 将所有元素存储在同一个存储单元B. 将所有元素存储在同一个链表中C. 将所有元素存储在同一个数组中D. 将所有元素存储在同一个链表的同一个位置答案：B7. 在图的遍历中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。

A. 遍历的顺序不同B. 遍历的起点不同C. 遍历的路径不同D. 遍历使用的存储结构不同答案：D8. 快速排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B9. 归并排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 在二叉搜索树中，查找一个元素的时间复杂度为（）。

A. O(n)B. O(logn)C. O(n^2)D. O(1)答案：B二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度通常用______来描述。

答案：大O符号2. 线性表的两种基本操作是插入和______。

2022年厦门理工学院数据科学与大数据技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、设计实时操作系统时，首先应该考虑系统的（）。

A.可靠性和灵活性B.实时性和可靠性C.分配性和可靠性D.灵活性和实时性2、下列观点中，不是描述操作系统的典型观点的是（）。

A.操作系统是众多软件的集合B.操作系统是用户和计算机之间的接口C.操作系统是资源的管理者D.操作系统是虚拟机3、死锁与安全状态的关系是（）。

A.死锁状态有可能是安全状态B.安全状态有可能成为死锁状态C.不安全状态就是死锁状态D.死锁状态一定是不安全状态4、关于临界问题的一个算法（假设只有进程P0和P1，能会进入临界区）如下（i为0或1代表进程P0或者P1）：Repeatretry：if（turn！=-1）turn=i；if（turn！=i）go to retry；turn=-1；临界区：turn=0；其他区域；until false；该算法（）。

A.不能保持进程互斥进入临界区，且会出现“饥饿”B.不能保持进程互斥进入临界区，但不会出现“饥饿”C.保证进程互斥进入临界区，但会出现“饥饿”D.保证进程互斥进入临界区，不会出现“饥饿”5、在个交通繁忙的十字路口，每个方向只有一个车道，如果车辆只能向前直行，而不允许转弯和后退，并未采用任何方式进行交通管理。

下列叙述正确的是（）。

A.该十字路口不会发生死锁，B.该十字路口定会发生死锁C.该上字路口可能会发生死锁，规定同时最多3个方向的车使用该十字路是最有效的方法D.该十字路口可能会发生死锁，规定南北方向的两个车队和东西方向的两个车队互斥使用十字路口是最有效的方法6、为了使多个进程能有效地同时处理输入和输出，最好使用（）结构的缓冲技术。

A.缓冲池B.循环缓冲C.单缓冲D.双缓冲7、虚拟设备是通过（）技术实现的。

A.并行B.通道C.SPOOLingD.虚拟存储8、若文件f1的硬链接为f2，两个进程分别打开fl和f2，获得对应的文件描述符为fd1和fd2，则下列叙述中，止确的是（）I.fl和f2的读写指针位置保持相同II.fl和f2共享同个内存索引节点III.fdl 和fd2分别指向各自的用户打开文件表中的一项，A.仅IIB. 仅II、IIIC.仪I、IID. I、II和II9、下列算法中，用于磁盘调度的是（），A.时间片轮转法B.LRU算法C.最短寻道时间优先算法D.高优先级算法10、有一个矩阵为100行x200列，即a[100][200]。

2021年厦门理工学院数据科学与大数据技术专业《计算机组成原理》科目期末试卷B（有答案）一、选择题1、有效容量为128KB的Cache，每块16B，8路组相联。

字节地址为1234567H的单元调入该Cache，其tag应为（）。

A.1234HB.2468HC.048DHD.12345H2、采用指令Cache与数据Cache分离的主要目的是（）。

A.降低Cache的缺失损失B.提高Cache的命中率C.降低CPU平均访存时间D.减少指令流水线资源冲突3、常用的（n，k）海明码中，冗余位的位数为（）。

A.n+kB.n-kC.nD.k4、下列说法正确的是（）。

A.当机器采用补码表示时，0有两种编码方式B.当机器采用原码表示时，0有两种编码方式C.当机器采用反码表示时，0有一种编码方式D.无论机器数采用何种码表示，0都有两种编码方式5、由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（）。

A.-126B.-125C.-32D.-36、系统总线中的数据线、地址线、控制线是根据（）来划分的。

A.总线所处的位置B.总线的传输方向C.总线传输的内容D.总线的材料7、在集中式总线控制中，响应时间最快的是（）。

A.链式查询B.计数器定时查询C.独立请求D.分组链式查询8、将高级语言源程序转换为机器目标代码文件的程序是（）。

A.汇编程序B.链接程序C.编译程序D.解释程序9、下列选项中，能缩短程序执行时间的措施是（）。

1.提高CPU时钟频率Ⅱ.优化数据通路结构ll.对程序进行编译优化A.仪I、ⅡB.仅I、ⅢC.仅Ⅱ、ID.I、Ⅱ、Ⅲ10、下列部件中不属于执行部件的是（）。

A.控制器B.存储器C.运算器D.外部设备11、（）不是常用三级时序系统中的一级。

A.指令周期B.机器周期C.节拍D.定时脉冲12、在下列寻址中，（）寻址方式需要先运算再访问主存。

A.立即B.变址C.间接D.直接13、假设相对寻址的转移指令占两个字节，第一个字节为操作码，第二个字节为位移量（用补码表示），每当CPU从存储器取出一个字节时，即自动完成（PC）+l-PC。

《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。

6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。

7. 树的根结点的度为______，度为0的结点称为______。

8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。

三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。

10. 简述二叉树的遍历方法。

11. 简述图的存储结构及其特点。

四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。

13. 编写一个算法，实现队列的出队操作。

五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。

15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。

答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。

“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。

A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )。

A.n—l条有向边B.n条有向边C.n(n—1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。

A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、——和——四种。

2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。

4．在一棵高度为h的3叉树中，最多含有——结点。

5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。

单元练习3一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）栈是运算受限制的线性表。

（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。

（ㄨ）（3）栈一定是顺序存储的线性结构。

（√）（4）栈的特点是“后进先出”。

（ㄨ）（5）空栈就是所有元素都为0的栈。

（ㄨ）（6）在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。

（√）（7）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。

（ㄨ）（8）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。

（ㄨ）（9）递归定义就是循环定义。

（√）（10）将十进制数转换为二进制数是栈的典型应用之一。

二．填空题（1）在栈结构中，允许插入、删除的一端称为栈顶。

（2）在顺序栈中，当栈顶指针top=-1时，表示栈空。

（3）在有n个元素的栈中，进栈操作的时间复杂度为 O（1）。

（4）在栈中，出栈操作的时间复杂度为：O(1) 。

（5）已知表达式，求它的后缀表达式是栈的典型应用。

（6）在一个链栈中，若栈顶指针等于NULL，则表示栈空。

（7）向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p->next=top；和top=p；操作。

（8）顺序栈S存储在数组 S->data[0..MAXLEN-1]中，进栈操作时要执行的语句有：S->top ++ 。

（或= S->top+1）（9）链栈LS，指向栈顶元素的指针是LS->next 。

（10）从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。

（11）由于链栈的操作只在链表的头部进行，所以没有必要设置头结点。

（12）已知顺序栈S，在对S进行进栈操作之前首先要判断栈是否满。

（13）已知顺序栈S，在对S进行出栈操作之前首先要判断栈是否空。

（14）若内存空间充足，链栈可以不定义栈满运算。

（15）链栈LS是空的条件是 LS->next=NULL 。

2022年厦门理工学院数据科学与大数据技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、一个存储器系统中，常常同时包含ROM和RAM两种类型的存储器，如果用lK×8位的ROM芯片和lK×4位的RAM芯片，组成4K×8位的ROM和1K×8位的RAM存储系统，按先ROM后RAM进行编址。

采用3-8译码器选片，译码信号输出信号为Y0~Y7，其中Y4选择的是（）。

A.第一片ROMB.第五片ROMC.第一片RAMD.第一片RAM和第二片RAM2、主存储器主要性能指标有（）。

1.存储周期Ⅱ.存储容量Ⅲ.存取时间Ⅳ.存储器带宽A.I、IⅡB.I、IⅡ、IVC. I、Ⅲ、lVD.全部都是3、有如下C语言程序段：（）short si=-32767；unsigned short usi=si；执行上述两条语句后，usi的值为A.-32767B.32767C.32768D.327694、4位机器内的数值代码，则它所表示的十进制真值可能为（）。

I.16 Ⅱ.-1 Ⅲ.-8 V.8A. I、V、ⅢB.IⅡ、IⅣC.Ⅱ、Ⅲ、IVD.只有V5、ALU属于（）。

A.时序电路B.控制器C.组合逻辑电路D.寄存器6、中断判优逻辑和总线仲裁方式相类似，下列说法中，正确的是（）。

I.在总线仲裁方式中，独立请求方式响应时间最快，是以增加处理器开销和增加控制线数为代价的II.在总线仲裁方式中计数器查询方式，若每次计数都从“0”开始，则所有设备使用总线的优先级相等III.总线仲裁方式一般是指I/O设备争用总线的判优方式，而中断判优方式一般是指I/O设备争用CPU的判优方式IV.中断判优逻辑既可以通过硬件实现，也可以通过软件实现，A. I，IIB. I，III，IVC. I，II，IVD.I，IV7、某机器I/O设备采用异步串行传送方式传送字符信息，字符信息格式为1位起始位、8位数据位、1位校验位和1位停止位。

数据结构期末考试试卷及答案一、选择题（每题2分，共20分）1. 下列哪一个不是线性结构的特点？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 有多个根结点D. 有且只有一个叶子结点答案：C2. 在单链表中，头结点的作用是（）A. 作为链表的起点B. 作为链表的终点C. 存储链表中的数据元素D. 作为链表中的第一个元素答案：A3. 在顺序表中，插入一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：B4. 下列哪种排序算法的平均时间复杂度最高？A. 冒泡排序B. 快速排序C. 直接插入排序D. 希尔排序答案：C5. 在二叉树中，具有3个结点的二叉树有（）种不同的形态。

A. 2B. 3C. 4D. 5答案：C6. 下列哪种情况不适合使用哈希表？A. 查找速度快B. 数据量较大C. 数据量较小D. 数据元素关键字分布均匀答案：C7. 在图的遍历过程中，下列哪种遍历方法属于深度优先遍历？A. 广度优先遍历B. 深度优先遍历C. 混合遍历D. 随机遍历答案：B8. 下列哪种数据结构不适用于实现栈？A. 顺序表B. 链表C. 树D. 图答案：C9. 在双向链表中，删除一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A10. 下列哪种情况不适合使用队列？A. 数据元素先进先出B. 数据元素后进先出C. 数据元素随机进出D. 数据元素按顺序进出答案：B二、填空题（每题2分，共20分）1. 线性表是具有______个数据元素的有限序列。

答案：n2. 在单链表中，每个结点包含两个域：数据域和______域。

答案：指针3. 在顺序表中，插入一个元素的时间复杂度是______。

答案：O(n)4. 快速排序的平均时间复杂度为______。

答案：O(nlogn)5. 哈希表中的冲突指的是______。

答案：不同的关键字对应同一存储位置6. 在图的遍历过程中，深度优先遍历算法使用的数据结构是______。

2022年厦门理工学院数据科学与大数据技术专业《计算机系统结构》科目期末试卷B（有答案）一、选择题1、利用时间重叠概念实现并行处理的是( )。

A.流水处理机B.多处理机C.并行（阵列）处理机D.相联处理机2、计算机组成设计不考虑( )。

A.专用部件设置B.功能部件的集成度C.控制机构的组成D.缓冲技术3、“启动I/O”指令是主要的输入输出指令，是属于（）。

A.目态指令B.管态指令C.目态、管态都能用的指令D.编译程序只能用的指令4、从计算机系统结构上讲，机器语言程序员所看到的机器属性是（）A.计算机软件所要完成的功能B.计算机硬件的全部组成C.编程要用到的硬件组织D.计算机各部件的硬件实现。

5、开发并行的途径有（），资源重复和资源共享。

A.多计算机系统B.多道分时C.分布式处理系统D.时间重叠6、计算机系统的层次结构按照由高到低的顺序分别为（）。

A.高级语言机器级，汇编语言机器级，传统机器语言机器级，微程序机器级B.高级语言机器级，应用语言机器级，汇编语言机器级，微程序机器级C.应用语言机器级，传统机器语言机器级，汇编语言机器级，操作系统机器级D.应用语言机器级，操作系统机器级，微程序机器级，传统机器语言机器级7、在操作系统机器级，一般用（）程序（）作业控制语句。

A.汇编程序，翻译B.汇编程序，解释C.机器语言，解释D.机器语言，翻译8、1TFLOPS计算机能力，1TBYTE/S的I/O带宽和（）称为计算机系统的3T性能目标。

A，1TBYTE 硬盘容量B.1TBYTE 软盘容量C.1TBYTE 主存容量D.A和B9、对机器语言程序员透明的是( )。

A.中断字B.主存地址寄存器C.通用寄存器D.条件码10、浮点数尾数基值rm=8，尾数数值部分长6位，可表示的规格化最小正尾数为( )A.0.5B.0.25C.0.125D.1/64二、填空题11、评价地址码个数不同的4种指令的优缺点的主要标准是________和________12、输入输出设备的异步性、实时性、与________三个特点是现代计算机系统必须具备的共同特性。

2022年厦门理工学院信息管理与信息系统专业《数据库概论》科目期末试卷B（有答案）一、填空题1、数据库恢复是将数据库从______状态恢复到______的功能。

2、关系规范化的目的是______。

3、DBMS的完整性控制机制应具备三个功能：定义功能，即______；检查功能，即______；最后若发现用户的操作请求使数据违背了完整性约束条件，则采取一定的动作来保证数据的完整性。

4、在VB 6.0中，已经用Adobel连接到数据库，并已绑定到数据库中的某个关系表，现要通过此控件向表中插入数据，需要用到Adobel.Recordset的_____方法和Update方法，使用Adobel.Recordset的_____方法可以使当前行指针在结果集中向前移动一行。

5、如果多个事务依次执行，则称事务是执行______；如果利用分时的方法，同时处理多个事务，则称事务是执行______。

6、在RDBMS中，通过某种代价模型计算各种查询的执行代价。

在集中式数据库中，查询的执行开销主要包括______和______代价。

在多用户数据库中，还应考虑查询的内存代价开销。

7、主题在数据仓库中由一系列实现。

一个主题之下表的划分可按______、______数据所属时间段进行划分，主题在数据仓库中可用______方式进行存储，如果主题存储量大，为了提高处理效率可采用______方式进行存储。

8、设在SQL Server 2000环境下，对“销售数据库”进行的备份操作序列如下图所示。

①出现故障后，为尽可能减少数据丢失，需要利用备份数据进行恢复。

首先应该进行的恢复操作是恢复_____，第二个应该进行的恢复操作是恢复_____。

②假设这些备份操作均是在BK设备上完成的，并且该备份设备只用于这些备份操作，请补全下述恢复数据库完全备份的语句RESTORE_____FROM BKWITH FILE＝1，_____；9、关系数据库中基于数学的两类运算是______________和______________。

2022年厦门理工学院数据科学与大数据技术专业《数据库系统原理》科目期末试卷A（有答案）一、填空题1、数据仓库主要是供决策分析用的______，所涉及的数据操作主要是______，一般情况下不进行。

2、数据库内的数据是______的，只要有业务发生，数据就会更新，而数据仓库则是______的历史数据，只能定期添加和刷新。

3、有两种基本类型的锁，它们是______和______。

4、设某数据库中有商品表（商品号，商品名，商品类别，价格）。

现要创建一个视图，该视图包含全部商品类别及每类商品的平均价格。

请补全如下语句： CREATE VIEW V1（商品类别，平均价格）AS SELECT商品类别，_____FROM商品表GROUP BY商品类别；5、数据模型是由______________、______________和______________三部分组成。

6、事务故障、系统故障的恢复是由______完成的，介质故障是由______完成的。

7、在数据库系统封锁协议中，一级协议：“事务在修改数据A前必须先对其加X锁，直到事务结束才释放X锁”，该协议可以防止______；二级协议是在一级协议的基础上加上“事务T在读数据R之前必须先对其加S锁，读完后即可释放S锁”，该协议可以防止______；三级协议是在一级协议的基础上加上“事务T在读数据R之前必须先对其加S锁，直到事务结束后才释放S锁”，该协议可以防止______。

8、在SQL Server 2000中，某数据库用户User在此数据库中具有对T 表数据的查询和更改权限。

现要收回User对T表的数据更改权，下述是实现该功能的语句，请补全语句。

_____UPDATE ON T FROM User；9、在一个关系R中，若每个数据项都是不可再分割的，那么R一定属于______。

10、关系数据库中基于数学的两类运算是______________和______________。

厦门理工《数据结构与算法》复习题一、选择题。

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 。

单元练习6一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）n维的多维数组可以视为n-1维数组元素组成的线性结构。

（√）（2）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。

（ㄨ）（3）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。

（√）（4）数组元素可以由若干个数据项组成。

（√）（5）数组的三元组表存储是对稀疏矩阵的压缩存储。

（ㄨ）（6）任何矩阵都可以进行压缩存储。

（ㄨ）（7）广义表是线性表的推广，所以广义表也是线性表。

（ㄨ）（8）广义表LS=（a0,a1,……an-1），则an-1是其表尾。

（√）（9）广义表((a,b),a,b)的表头和表尾是相等的。

（√）（10）一个广义表的表尾总是一个广义表。

二．填空题（1）多维数组的顺序存储方式有按行优先顺序存储和按列优先顺序存储两种。

（2）在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种随机存取结构。

（3）在n维数组中的每一个元素最多可以有 n 个直接前驱。

（4）输出二维数组A[n][m]中所有元素值的时间复杂度为O(n*m) 。

（5）数组元素a[0..2][0..3]的实际地址上2000，元素长度是4，则LOC[1,2]= 2024 。

LOC[1,2]=2000+（1*4+2）*4（6）稀疏矩阵的三元组有 3 列。

（7）稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的行数。

（8）n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1）/2 个存储单元。

（9）稀疏矩阵A如下图所示，其非零元素存于三元组表中，三元组（4，1，5）按列优先。

稀疏矩阵AA=（10）稀疏疏矩阵的压缩存储方法通常有三元组表和十字链表两种。

（11）任何一个非空广义表的表尾必定是广义表（或子表）。

（12）tail(head((a,b),(c,d))= b 。

（13）设广义表((a,b,c))，则将c分离出来的运算是 head(tail(tail(head(L)))) 。

单元练习9一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）二分查找法要求待查表的关键字值必须有序。

（ㄨ）（2）对有序表而言采用二分查找总比采用顺序查找法速度快。

（ㄨ）（3）在二叉排序树中，根结点的值都小于孩子结点的值。

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

（√）（5）哈希表是一种将关键字转换为存储地址的存储方法。

（ㄨ）（6）选择好的哈希函数就可以避免冲突的发生。

（ㄨ）（7）在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。

（√）（8）采用分块查找，既能实现线性表所希望的查找速度，又能适应动态变化的需要。

（√）（9）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。

（ㄨ）（10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。

二．填空题（1）顺序查找法，表中元素可以任意存放。

（2）在分块查找方法中，首先查找索引，然后再查找相应的块。

（3）顺序查找、二分查找、分块查找都属于静态查找。

（4）静态查找表所含元素个数在查找阶段是固定不变的。

（5）对于长度为n的线性表，若进行顺序查找，则时间复杂度为 O（n）。

（6）对于长度为n的线性表，若采用二分查找，则时间复杂度为： O（log2n）。

（7）理想情况下，在散列表中查找一个元素的时间复杂度为： O（1）。

（8）在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较 4 次才找到。

（9）设有100个元素，用二分查找时，最大的比较次数是 7 次。

（10）对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点小，则继续在左子树中查找。

（11）二叉排序树是一种动态查找表。

（12）哈希表是按散列存储方式构造的存储结构（13）哈希法既是一种存储方法，又是一种查找方法。

（14）散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。