数据结构期末考试(题集).doc

数据结构的基本概念选择题（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。A线性结构B非线性结构C存储位置D指针（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。A树B图C线性表D集合（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。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） 以下与数据的存储结构无关的术语是（ ）。A循环队列B链表C散列表D栈（9） 以下术语属于逻辑结构的是（ ）。A顺序表B哈希表C有序表D单链表（10） 可以用（ ）定义一个完整的数据结构。A数据元素B数据对象C数据关系D抽象数据类型（11） 对于数据结构的描述，下列说法中不正确的是（ ）。A相同的逻辑结构对应的存储结构也必相同B数据结构由逻辑结构、存储结构和基本操作三方面组成C数据结构基本操作的实现与存储结构有关D数据的存储结构是数据的逻辑结构的机内实现（12） 以下关于链接存储结构的叙述中，（ ）是不正确的。A结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构B逻辑上相邻的结点物理上不一定相邻C可以通过计算得到第i个结点的存储地址D插入和删除操作方便，不必移动结点（13） 可以用（ ）、数据关系和基本操作定义一个完整的抽象数据类型。A数据元素B数据对象C原子类型D存储结构应用题（14） 设有数据结构（D，R），其中D=1，2，3，4，5，6，R=(1，2)，(2，3)，(2，4)，(3，4)，(3，5)，(3，6)，(4，5)，(4，6)。试画出其逻辑结构图并指出属于何种结构。（15） 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。（16） 说明数据的逻辑结构和存储结构之间的关系。（17） 抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？1 算法和算法分析选择题（1） 算法指的是（ ）。A对特定问题求解步骤的一种描述，是指令的有限序列B计算机程序C解决问题的计算方法D数据处理（2） 下面（ ）不是算法所必须具备的特性。A有穷性B确切性C高效性D可行性（3） 算法必须具备输入、输出和（ ）等特性。A可行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性、稳定性和有穷性D易读性、稳定性和健壮性（4） 算法应该具有确定性、可行性和有穷性，其中有穷性是指（ ）。A算法在有穷的时间内终止B输入是有穷的C输出是有穷的D描述步骤是有穷的（5） 当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果，这称为算法的（ ）。A可读性B健壮性C正确性D有穷性（6） 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性（7） 算法的时间复杂度与（ ）有关。A问题规模B计算机硬件性能C编译程序的质量D程序设计语言（8） 算法的时间复杂度与（ ）有关。A问题规模B待处理数据的初态C算法的易读性DA和B（9） 某算法的时间复杂度是(n2)，表明该算法（ ）。A问题规模是n2B执行时间等于n2C执行时间与n2成正比D问题规模与n2成正比（10） 下面说法错误的是（ ）。算法原地工作的含义是指示不需要如何额外的辅助空间在相同的规模n下，复杂度(n)的算法在时间上总是优于复杂度(2n)的算法所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效率就越低（11） 算法for (i=n-1; i=1; i-)for (j=1; jaj+1) aj与aj+1交换；其中n为正整数，则最后一行语句的频度（执行次数）在最坏情况下是（ ）。A(n)B(nlog2n)C(n3)D(n2)（12） 算法的时间复杂度属于一种（ ）。A事前统计的方法B事先分析估算的方法C事后统计的方法D事后分析估算的方法（13） 设某算法完成对n个元素进行处理，所需的时间是T(n)=100 nlog2n+200n+500，则该算法的时间复杂度是（ ）。A(1)B(n)C(nlog2n)D(nlog2n+n)（14） 假设时间复杂度为(n2)的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上运行需要（ ）ms。A3.1B6.2C12.4Dx（无法确定）（15） 下列程序段加下划线的语句执行（ ）次。for (m=0,i=1; i=1; i+)for (j=1; j=2*i; j+)m=m+1；An2B3nCn(n+1)Dn3应用题（16） 将下列函数按它们的n时的无穷大阶数，从小到大排列。n，n-n3-7n5，nlog2n，2n/2，n3，log2n，n1/2+log2n，(3/2)n，n!，n2+log2n（17） 分析以下程序段，并用大记号表示其执行时间。 i=1;k=0;while (in-1)k=k+10*i;i+; i=1;j=0;while (i+jj) j+;else i+; for (i=1;i=n;i+)for (j=1;j=i;j+)for (k=1;k=j;k+)x+; i=1;k=0;dok=k+10*i;i+; while (i=n) y=0;while (y+1)*(y+1)=n)y=y+1 for (i=0;in;i+)for (j=0;jm;j+)aij=0;（18） 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为T1=(2n)，A2的时间复杂度为T2=(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。综合应用题（19） 设n是偶数，且有程序段：for (i=1;i=n;i+)if (2*i=n)for (j=2*I;jnext=p-next-nextBp-next=p-nextCp=p-next-nextDp=p-next; p-next=p-next-next（8） 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（ ）操作。As-next=p-next; p-next=s;Bq-next=s; s-next=p;Cp-next=s-next; s-next=p;Dp-next=s; s-next=q（9） 在一个长度为n（n1）的带头结点的单链表h上，另设有尾指针r指向尾结点，执行（ ）操作与链表的长度有关。A删除单链表中的第一个元素B删除单链表中的最后一个元素C在单链表第一个元素前插入一个新元素D在单链表的最后一个元素后插入一个新元素（10） 在单链表中附加头结点的目的是为了（ ）。A保证单链表中至少有一个结点B标识单链表中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储（11） 将长度为n个单链表链接在长度为m的单链表之后的算法，其时间复杂度是（ ）。A(1)B(n)C(m)D(n+m)（12） 循环单链表的主要优点是（ ）。A不再需要头指针了B从表中任一结点出发都能扫描到整个链表C已知某个结点的位置后，能够容易找到它的直接前驱D在进行插入、删除操作时，能更好地保证链表不断开（13） 将线性表（a1，a2，an）组织为一个带头结点的循环单链表，设H为链表的头指针，则链表中最后一个结点的指针域中存放的是（ ）。A变量H的地址B变量H的值C元素a1的地址D空指针（14） 非空的循环单链表L的尾结点p满足（ ）。Ap=NULLBp-next=NULLCp-next=LDp=L（15） 若要在(1)的时间内实现两个循环单链表的首尾相接，则两个循环单链表应各设一个指针，分别指向（ ）。A各自的头结点B各自的尾结点C各自的第一个元素结点D一个表的头结点，一个表的尾结点（16） 设线性表非空，（ ）可以在(1)的时间内在表尾插入一个新结点。A带头结点的单链表，有一个链表指针指向头结点B带头结点的循环单链表，有一个链表指针指向头结点C不带头结点的单链表，有一个链表指针指向表的第一个结点D不带头结点的循环单链表，有一个链表指针指向表中某个结点（除第一个结点外）（17） 设指针rear指向带头结点的循环单链表的尾指针，若要删除链表的第一个元素结点，正确的操作是（ ）。As=rear; rear=rear-next;Brear=rear-next;Crear=rear-next-next;Ds=rear-next-next; rear-next-next=s-next;（18） 设有两个长度为n个单链表，以h1为头指针的链表是非循环的，以h2为尾指针的链表是循环的，则（ ）。A在两个链表上删除第一个结点的操作，其时间复杂度均为(1)B在两个链表的表尾插入一个结点的操作，其时间复杂度均为(n)C循环链表要比非循环链表占用更多的存储空间D循环链表要比非循环链表占用更少的存储空间（19） 使用双链表存储线性表，其优点是可以（ ）。A提高查找速度B更方便数据的插入和删除C节约存储空间D很快回收存储空间（20） 与单链表相比，双链表的优点之一是（ ）。A插入和删除操作更简单B可以进行随机访问C可以省略表头指针或表尾指针D访问其后相邻结点更灵活（21） 带头结点的循环双链表L为空表的条件是（ ）。AL-next-prior=NULLBL-prior=LCL-next=LDB和C都对（22） 在循环双链表的p所指结点后插入s所指结点的操作是（ ）。Ap-next=s; s-prior=p; p-next-prior=s; s-next=p-next;Bp-next=s; p-next-prior=s; s-prior=p; s-next=p-next;Cs-prior=p; s-next=p-next; p-next=s; p-next-prior=s;Ds-prior=p; s-next=p-next; p-next-prior=s; p-next=s;（23） 在双链表中指针pa所指结点后面插入pb所指结点，执行的语句序列是（ ）。pb-next=pa-next;pb-prior=pa;pa-next=pb;pa-next-prior=pb;ABCD（24） 在一个双链表中，删除结点p的操作是（ ）。Ap-prior-next=p-next; p-next-prior=p-prior;Bp-prior=p-prior-prior; p-prior-prior=p;Cp-next-prior=p; p-next=p-next-next;Dp-next=p-prior-prior; p-prior=p-prior-prior;应用题（25） 单链表设置头结点的作用是什么？（26） 线性表的顺序存储结构具有三个弱点：其一，插入或删除操作需要移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。试问，线性表的链接存储结构是否能够克服上述三个弱点？（27） 若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较好？（28） 设n表示线性表中的元素个数，P表示指针所需的存储单元大小，E表示存储数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间（不考虑头结点）？算法设计题（29） 设计算法依次打印单链表中每个结点的数据信息。（30） 求单链表的长度。（31） 设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前，若找不到值为k的结点，则将x插入到链表的末尾。（32） 判断非空单链表是否递增有序。（33） 已知非空线性链表由list指出，结点结构为（data，link）。请编写算法，将链表中数据域最小的结点移到链表的最前面。要求：不得额外申请新的结点。（34） 给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。（35） 已知非空线性链表由list指出，设计算法交换p所指结点与其后续结点在链表中的位置（设p所指结点不是链表的最后一个结点）。（36） 设计算法实现将单链表就地逆置。（37） 头插法建立单链表。（38） 尾插法建立单链表（39） 复制一个单链表。（40） 设计算法实现将单链表就地逆置。（41） 在一个有序单链表（假设从小到大排列）中插入一个元素值为x的结点，使得插入后单链表仍然有序。（42） 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。（43） 已知单链表中各结点的元素值为整型且递增有序，设计算法删除表中大于mink且小于maxk的所有元素，并释放被删结点的存储空间。（44） 有两个整数序列A=(a1，a2，am)和B=(b1，b2，bn)已经存入两个单链表中，设计算法判断序列B是否是序列A的子序列。（45） 设线性表C=(a1，b1，a2，b2，an，bn)采用带头结点的单链表存储，设计算法将表C拆分为两个线性表A和B，使得A=(a1，a2，an)，B=(b1，b2，bn)。（46） 有两个递增有序的单链表la和lb，设计算法将这两个单链表合并为一个有序链表。（47） 有两个有序的单链表，一个表为升序，另一个表为降序，设计算法将这两个链表合并为一个有序链表。（48） 已知单链表A和B的数据（设为整型）递增有序，设计算法利用原有结点，将表A中与表B具有相同值的结点删除，将表B中与原表A不同值的结点存入表A中，并保持表A的递增有序。（49） 设计算法将循环单链表就地逆置。（50） 已知L为单链表的头结点地址，表中共有m（m3）个结点，从表中第i个（1im）结点起到第m个结点构成一个部分循环链表。设计算法将这部分循环链表中所有结点顺序完全倒置。（51） 假设在长度大于1的循环单链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前驱结点。（52） 设循环单链表L1，对其遍历的结果是：x1，x2，x3，xn-1，xn。请将该循环链表拆成两个循环单链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1，x3，；L2中含有原L1表中序号为偶数的结且遍历结果为：，x4，x2。（53） 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环单链表，使每个循环链表中只含同一类字符。（54） 有两个循环链表tail1和tail2（tail1和tail2分别指向循环链表的尾指针），编写算法将循环链表tail2链接到循环链表tail1之后，并使链接后的链表仍是循环链表。（55） 已知p指向循环单链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表（a1，a2，an-1，an，）改造成（a1，a2，an-1，an，an-1，a2，a1）。（56） 判断带头结点的循环双链表是否对称。（57） 设计算法实现双链表中第i个结点的前面插入一个值为x的结点。（58） 已知非空循环双链表head的存储结构为：Struct DNode TElem info;Struct DNode *left;Struct DNode *right;设计算法实现从链表中删除指针p所指结点的前驱结点（假设该结点存在）。（59） 已知非空双链表由d指出，结点结构为（priordatanext），请设计算法将链表中数据值最大（假定唯一）的那个结点移至链表的最前面。要求不得额外申请新的双链表结点。（60） 设计算法实现将双链表中结点p与其后继结点互换位置。（61） 设有一个双链表，每个结点中除了有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零，每当在双链表上进行一次LOCATE运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。编写算法实现符合上述要求的LOCATE算法。5 静态链表选择题（1） 静态链表中指针表示的是（ ）。A下一结点在内存中的地址B下一元素在数组中的下标C左、右孩子的存储位置D左、右孩子的地址（2） 以下说法错误的是（ ）。静态链表既有顺序存储的优点又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关静态链表中能容纳的元素个数在定义表时必须是确定的静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动A，BC，D（3） 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中某结点，使j沿链移动的操作为（ ）。Aj=rj.nextBj=j+1Cj=j-nextDj=rj-next（4） 线性表的静态链表存储与顺序存储相比，优点是（ ）。A所有基本操作的算法实现简单B便于随机存取C便于插入和删除D便于利用零散的存储空间（5） 下图所示数组中以静态链表形式存储了一个线性表，设头指针为a0.link，则该线性表的元素依次为（ ）。下标012345678data606340457425link4376201A60，63，40，45，74，25B45，63，25，60，40，74C74，25，45，60，40，63D25，45，60，40，63，746 线性表综合选择题（1） 下面关于线性表的叙述中，错误的是（ ）。A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作C线性表采用链接存储，不必占用一片连续的存储单元D线性表采用链接存储，便于插入和删除操作（2） 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用（ ）存储方法最节约时间。A顺序表B单链表C双链表D循环单链表（3） 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节约时间。A单链表B循环双链表C循环单链表D带尾指针的循环单链表（4） 设线性表有n个元素，以下操作中，（ ）在顺序表上实现比在链表上实现的效率更高。A输出第i（1in）个元素值B交换第1个和第2个元素的值C顺序输出所有n个元素D查找与给定值x相等的元素在线性表中的序号（5） 如果对于具有n（n1）个元素的线性表的基本操作有4种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素的后面插入新元素。则最好使用（ ）。A只设尾指针的循环单链表B只设尾指针的非循环单链表C只设头指针的循环双链表D同时设置头指针和尾指针的循环单链表应用题（6） 请比较线性表的两种基本的存储结构顺序表和单链表。（7） 举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，算法的效率不同。（8） 如果某线性表中数据元素的类型不一致，但是希望能根据下标随机存取每个元素，请为这个线性表设计一个合适的存储结构。（9） 线性链表有哪几种常见的变形？各有何特点？算法设计题（10） 用顺序表表示集合，设计算法实现集合的求交集运算。（11） 用顺序表表示集合，设计算法实现集合的求并集运算。（12） 用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。（13） 假定以有序表表示集合，设计算法判断两个给定集合是否相等。（14） 设两个单链表L1和L2分别表示两个集合，设计算法判断L1是否是L2的子集。（15） 已知两个不带头结点的单链表A和B分别表示两个集合，并且其元素值递增有序，求A、B的交集C，并以同样的递增形式存储，要求尽可能节省时间。（16） 在某商店的仓库中，对电视机按其价格从低到高建立一个单链表，链表的每个结点指出同样价格的电视机的台数。现有m台价格为n元的电视机入库，请编写算法完成仓库的进货管理。（17） 从键盘输入n个英语单词，输入格式为n，w1，w2，wn，其中n表示随后输入英语单词个数，试编写算法建立一个单链表，要求：如果单词重复出现，则只在链表上只保留一个；统计单词重复出现的次数，然后输出次数最多的前k（kn）个单词。（18） 一元稀疏多项式可以采用单链表形式存储，设计算法完成A(x)+B(x)，其中A(x)和B(x)均为稀疏的一元多项式，要求利用原表的存储空间。（19） 假设用不带头结点的单链表表示八进制数，例如，八进制数536可以表示成三个结点的链表。要求写一个函数Add，该函数有两个参数P和Q，分别指向表示八进制数的链表，执行函数调用Add(P,Q)后，将返回表示八进制数P加八进制数Q所得结果数的链表。（20） 约瑟夫环问题：设有编号为1，2，n的n（n0）个人围成一个圈，每个人持有一个密码m（m1），从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。（21） 编写算法，完成下述要求：建立一个链表用于存放输入的二进制数，链表中的每个结点的data域存放一个二进制位。在此链表上实现对二进制数加1的运算，并输出运算结果。（22） 有一个不带头结点的单链表h，通过遍历链表将链表中所有的链接方向逆转，算法如下，请在空格处填写正确的语句。void Inverse(&h) if ( ) return;p=h-next; pr=NULL;while ( ) h-next=pr;pr=h;h=p; （23） 设两个带头结点的单链表A和B，表中结点的数据为整型，下面算法产生表A和表B的并集并以表C存储，请填写算法中空白处的语句，完成其功能。7 栈的基本概念选择题（1） 经过以下栈运算后，x的值是（ ）。InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，GetTop(s,x)AaBbC1D0（2） 经过以下栈运算后，StackEmpty(s)的值是（ ）。InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，Pop(s,y)AaBbC1D0（3） （ ）不是栈的基本运算。A删除栈顶元素B删除栈底元素C判断栈是否为空D将栈置为空栈（4） 设有一个空栈，栈顶指针为1000H（十六进制，下同），每个元素需要1个单位的存储空间，则执行PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH操作后，栈顶指针值为（ ）。A1002HB1003HC1004HD1005H（5） 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ ）。A5，4，3，2，1B4，5，3，2，1C4，3，5，1，2D1，2，3，4，5（6） 若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。A不确定Bn-iCn-i-1Dn-i+1（7