西北民族大学数据结构题库(1)

数据结构试卷（一）王彬一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

一.选择题A.16B.32C. 4 8D.64 9 .设［X ］补当满足 _________________ 时，X>-1/2成立。

A .x 2x 3x 4至少有一个为1 B. Xi 必须为1，x 2x 3x 4任意 C . Xi 必须为0，x 2x 3x 4至少有一个为1D . Xi 必须力0，x 2x 3x 4任意10. CPU 主要包拈 ______ 。

A.控制器B.控制器、运算器、cacheC.运算器和主存D.控制器、ALU 和主存 11. 信息只用一条传输线，且采用脉冲传输的方式称为 ________ 。

A.串行传输B.并行传输C.并串行传输D.分时传输 12. 以下四种类型指令中，执行时间最长的是 _______ 。

A. RR 型B. RS 型C. SS 型D.程序控制指令 13. 下列 _____ 属于应用软件。

A.操作系统B.编译系统C.连接程序D.文本处理 14. 在主存和CPU 之间增加cache 存储器的目的是 ________ 。

A.增加内存容量B.提高内存可靠性C.解决CPU 和主存之间的速度匹配问题D.增加内存容量，冋时加快存取速度 15. 某单片机的系统程序，不允许用户在执行时改变，则可以选用 ________ 作为存储芯片。

A. SRAMB.闪速存储器C. cacheD.辅助存储器 16. 设变址寄存器为X ，形式地址为D, (X)表示寄存器X 的内容，这种寻址方式的有效地址为 ______ 。

A. EA=(X)+DB. EA=(X)+(D)C.EA=((X)+D)D. EA=((X)+(D))17. 在指令的地址字段中，直接指出操作数本身的寻址方式，称为 ________ 。

习题一1. 目前我们所说的个人台式商用机属于 _______ 。

A.巨型机B.中型机C.小型机D.微型机2. (2000) i 。

化成十六进制数是 _______ 。

A. (7CD) 16 B 。

2021年西北民族大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、主存与Cache间采用全相联映射方式，Cache容量4MB，分为4块，每块lMB，主存容量256MB。

若主存读/写时间为30ms，Cache的读/写时间为3ns，平均读/写时间为3.27ms，则Cache的命中率为（）。

A.90%B.95%C.97%D.99%2、下述说法中正确的是（）。

I.半导体RAM信息可读可写，且断电后仍能保持记忆Ⅱ.动态RAM是易失性RAM，而静态RAM中的存储信息是不易失的Ⅲ.半导体RAM是易失性RAM，但只要电源不断电，所存信息是不丢失的IV.半导体RAM是非易失性的RAMA.I、ⅢB.只有ⅢC.Ⅱ、IVD.全错3、某字长为8位的计算机中，已知整型变量x、y的机器数分别为[x]补=11110100，[y] 补=l0110000。

若整型变量z=2x+y/2，则z的机器数为（）。

A.11000000B.00100100C.10101010D.溢出4、一个C语言程序在一台32位机器上运行，程序中定义了3个变量x、y、z，其中x 和z是int型，y为short型。

当x=127，y=-9时，执行赋值语句z=xty后，x、y、z的值分别是（）。

A.x=0000007FH，y=FFF9H，z=00000076HB.x=0000007FH，y=FFF9H，z=FFFFO076HC.X=0000007FH，y-FFF7H，z=FFFF0076HD.X=0000007FH，y=FFF7H，z=00000076H5、串行运算器结构简单，其运算规律是（）。

A.由低位到高位先行进行进位运算B.由低位到高位先行进行借位运算C.由低位到高位逐位运算D.由高位到低位逐位运算6、系统总线中的数据线、地址线、控制线是根据（）来划分的。

A.总线所处的位置B.总线的传输方向C.总线传输的内容D.总线的材料7、在下面描述的PCI总线的基本概念中，不正确的表述是（）。

数据构造习题集含答案目录目录 (1)选择题 (2)第一章绪论 (2)第二章线性表 (4)第三章栈和队列 (6)第四章串 (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图 (11)第八章查找 (13)第九章排序 (14)简答题 (19)第一章绪论 (19)第二章线性表 (24)第三章栈和队列 (26)第四章串 (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图 (36)第八章查找 (38)第九章排序 (39)编程题 (41)第一章绪论 (41)第二章线性表 (41)第三章栈和队列 (52)第四章串 (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图 (52)第八章查找 (52)第九章排序 (57)选择题第一章绪论1.数据构造这门学科是针对什么问题而产生的？〔A〕A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据构造这门学科的研究内容下面选项最准确的是〔D〕A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得X三同学的各科成绩记录，其中数据构造考了90分，那么下面关于数据对象、数据元素、数据项描述正确的选项是〔C〕A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.*数据构造是指〔A〕。

A、数据元素的组织形式B、数据类型C、数据存储构造D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不一样，称之为〔C〕。

A、存储构造B、逻辑构造C、链式存储构造D、顺序存储构造6.算法分析的目的是〔C〕A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改良D、分析算法的易懂性和文档型性7.算法分析的主要方法〔A〕。

数据结构习题(有答案) 第１章绪1。

1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。

（1) A= （ D,R )，其中,D = { ａ1，ａ2,ａ３，a４}, R={ ｝(2） B= （ D,R ),其中，D = ｛ a，ｂ,c,d，ｅ｝, R＝｛ (a,ｂ),(ｂ，c），（c，d）,(d，e）｝（3) C= （ D，Ｒ），其中，D = ｛ a，b，c,d，ｅ,f，g}, R=｛（d,b)，(d,g），(1）集合(2) 线性表a b c d e(３）树fgabcde(4）图1453621 / 48·····谢阅。

（b,a),（ｂ，c),（ｇ，e），（e，f)}（4) K= （ D,R ），其中,Ｄ= ｛ 1，2，3,4，5，６}, R=｛〈1，2＞,〈2，3＞，〈2，4＞，<3，４>，<３，５>，＜3，6>,<4,5〉,〈４，6〉}1.２设n为正整数,求下列各程序段中的下划线语句的执行次数。

（1) i=1；ｋ=0ｗhiｌe(i 〈=n-1){k+=１0＊i ；i＋+;（2) fｏr （ｉnt i=１；ｉ＜=n； i+＋）ｆor （int j＝１; j〈=ｎ; ｊ+＋)｛ｃ［i］［j］=0；解:(１) n－1（2) ∑∑∑====ninjnkn111312 / 48·····谢阅。

｝ﻩ fｏr(inｔk=1； k〈=n; ｋ＋＋）c[ｉ]［j］=c[i］［j]+a[ｉ］［k]*ｂ［k］[j］｝（3) x=０；ｙ=０;for （int ｉ＝1; i＜=n; i++)fｏr (inｔ j=1; j<＝ｉ; ｊ+＋)for (inｔk=1; k〈＝ｊ; k ＋＋）(３）62)1)(nn(n21)(216)12)(1(2121212)1(1112111111++=+•+++•=+=+==∑∑∑∑∑∑∑∑========nnnnniii ijnininiijjkniijni3 / 48·····谢阅。

2022年西北民族大学数据科学与大数据技术专业《计算机网络》科目期末试卷B（有答案）一、选择题1、当数据由主机A送传至主机B时，不参与数据封装工作的是（）。

A.物理层B.数据链路层C.网络层D.传输层2、世界上第一个计算机网络是（）。

A.ARPANETB.因特网C.NSFnetD.CERNET3、互联网规定的B类私有地址为（）。

A.172.16.0.0/16B.172.16.0.0/12C.172.15.0.0/16D.172.15.0.0/124、因特网的RIP、OSPF协议、BGP分别使用了什么路由选择算法（）。

I.路径-向量路由选择协议Ⅱ.链路状态协议Ⅲ.距离-向量路由选择协议A.I、Ⅱ、IⅡB. Ⅱ、Ⅲ、IC.Ⅱ、I、IⅢD.Ⅲ、Ⅱ、I5、主机甲通过128kbit/s卫星链路，采用滑动窗口协议向主机乙发，送数据，链路单向传播延迟为250ms，帧长为1000字节。

不考虑确认帧的开销，为使链路利用率不小于80%，帧序号的比特数至少是（）A.3B.4C.7D.86、为了纠正2比特的错误，编码的海明距应该为（）。

A.2B.3C.4D.57、下列关于传输层协议中面向连接的描述，（）是错误的。

A.面向连接的服务需要经历3个阶段：连接建立、数据传输以及连接释放B.面向连接的服务可以保证数据到达的顺序是正确的C.面向连接的服务有很高的效率和时间性能D.面向连接的服务提供了一个可靠的数据流8、使用两种编码方案对比特流01100111进行编码的结果如图所示，编码1和编码2分别是（）A.NRZ 和曼彻斯特编码B.NRZ 和差分曼彻斯特编码C.NRZ-I和曼彻斯特编码D.NRZ-I和差分曼彻斯特编码9、有一条TCP连接，它的最大报文段长度为2KB，TCP拥塞窗口为24KB，这时候发生了超时事件，那么该拥塞窗口变成了（）。

A.1KBB.2KBC.5KBD.7KB10、下列关于FTP协议的叙述中，错误的是（）A.数据连接在每次数据传输完毕后就关闭B.控制连接在整个会话期间保持打开状态C.服务器与客户端的TCP 20端口建立数据连接D.客户端与服务器的TCP 20端口建立控制连接11、下列关于FTP的描述，（）存在错误。

西北民族大学计算机科学与信息工程学院期中考试数据结构试卷（ A 卷）专业: 课程代码:学号: 姓名:一、选择题（在每小题的四个备选答案中，选出一个正确的答Array案，并将其代码填入题干后的括号内。

每小题 2 分，共 40 分）1．从逻辑上可以把数据结构分为（ C ）。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.结性结构和非线性结构D.内部结构和外部结构2. 下面程序的时间复杂度为（ C ）。

For (i=0; i<m; i++)For (j=0; j<n; j++)A[i][j]=i*j;A. O(m2)B. O(n2)C. O(m×n)D.O(m+n)3．带头结点的单链表head为空的判断条件是（ B ）。

A.head=NULLB.head->next=NULLC.head->next＝D.head!=NULL4．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.又链表D.仅有尾指针的单循环链表5．线性表的静态链表存储结构与顺序存储结构优点是（B）。

A.所有的操作算法简单B.便于插入和删除C.便于利用零散的存储器空间D.便于随机存取6．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（A）。

A. nB. 2n-1C. 2nD. n-1数据结构试卷第1页（共6页）7．在双循环链表p所指结点之后插入s所指结点的操作是（D）。

A. p->next=s; s->prior=p; p->next->prior=s; s->prior=p->next;B. p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;C. s->prior=s; s->next=p->next; p->next=s; p->next->prior=s;D.s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;8．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为（C）。

2022年西北民族大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并2、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)3、以下与数据的存储结构无关的术语是（）。

A.循环队列B.链表C.哈希表D.栈4、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、动态存储管理系统中，通常可有（）种不同的分配策略。

A.1B.2C.3D.46、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。

7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡A.LLB.LRC.RLD.RR二、填空题11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。

12、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用<a，b，d> 三元组表示弧<a，b>及弧上的权d。

数据结构试题库及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用（）来存储。

A. 链表B. 栈C. 队列D. 数组答案：D2. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序答案：C3. 在二叉树的遍历算法中，先访问根节点，然后遍历左子树，最后遍历右子树的遍历方式是（）。

A. 先序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A4. 哈希表的冲突解决方法不包括以下哪种？A. 链地址法B. 线性探测法C. 二分查找法D. 再散列法答案：C5. 在图的遍历算法中，广度优先搜索（BFS）使用的辅助数据结构是（）。

A. 栈B. 队列C. 堆D. 链表答案：B6. 下列关于堆的描述中，错误的是（）。

A. 堆是一种特殊的完全二叉树B. 堆中的每个节点的值都大于其子节点的值C. 堆可以用于实现优先队列D. 堆的插入操作的时间复杂度为O(log n)答案：B7. 在一个长度为n的数组中，使用二分查找算法查找一个元素的最坏情况下的时间复杂度是（）。

A. O(1)B. O(n)C. O(n^2)D. O(log n)答案：D8. 以下哪个数据结构不是线性结构？A. 链表B. 栈C. 队列D. 二叉树答案：D9. 以下哪个算法是动态查找表？A. 直接索引B. 顺序查找C. 二分查找D. 哈希表答案：D10. 在图的表示方法中，邻接矩阵表示法的缺点是（）。

A. 占用空间大B. 占用空间小C. 插入和删除操作复杂D. 遍历操作复杂答案：A二、填空题（每题2分，共20分）1. 在一个长度为n的数组中，使用顺序查找算法查找一个元素的时间复杂度为________。

答案：O(n)2. 一个具有n个节点的完全二叉树的高度为________。

答案：log2(n) + 1（向上取整）3. 一个长度为n的链表，删除一个节点的时间复杂度为________。

答案：O(1)4. 在图的表示方法中，邻接表表示法的缺点是________。