表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为( )。

admin2021-08-17 123

问题表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为( )。

选项 A、n
B、n／2
C、(n-1)／2
D、(n+1)／2

答案C

解析顺序表的删除运算时间主要消耗在移动表中元素上，删除第i个元素时，其后面的元素a_i+1～a_n都要向上移动一个位置，共移动了n一i个元素。在等概率情况下，即p_i=1／n，则：

这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为O(n)。

转载请注明原文地址:https://kaotiyun.com/show/4D3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一
设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：主存字地址有多少位?区号、区内块号和块内地址各多少位?
已知一个带有表头结点的单链表，结点结构为(data，next)，假设该链表只给出了头指针L，请设计一个时间和空间上尽可能高效的算法，将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。根据设计思想，采用C或C++或Java语言描述算法，关键之
设表7-2为路由器R的不完整的路由表(其中下一跳给出的是路由器的端口)。路由器R收到下述分别发往6个目的主机的数据报。H1：20．134．245．78H2：166．111．64．129H3：166．111．35．72
在一个段式存储管理系统中，逻辑地址为32位，其中高16位为段号，低16位为段内偏移，以下是段表(其中的数据均为十六进制，如表7-1所示)。以下是代码段的内容：试问：pushx指令的执行过程：将SP(堆栈寄存器)减4，然后存储x的值。试
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I／O设备读取1000B的数据到主存缓冲区中，该I／O设备一旦启动即按50KB／s的数据传输率向主机传送1000B数据，每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期，则以下4种
下列说法中，正确的是()。Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个
一个正在访问临界资源的进程由于申请等待I／O操作而被中断时()。
下列说法中，不正确的是()。

随机试题

两个或多个样本率／构成比的比较通常采用的是()
某村位于内陆地区，村民中得“粗脖子”病的人很多，经调查此地居民碘摄入不足。碘摄入不足会引起碘缺乏病，对人体产生多种危害，除了
下列方剂中未见大黄、栀子同用的是
首先将阴黄与阳黄辨证施治系统化的是
“喂养”和“饲养”的区别是()
一款安抚型机器人可以通过USB充电，续航达到8小时。目前其以100美元的价格进行众筹，预计明年上市。请解释“USB”和“众筹”。
Whichdistancedidtheytalkabout?
WelcomeSpeech1.Roomallocation.RoomnumberThebeginningletterreferstothethree【T1】________ofthecollege
Thesocialeffectsofjob-sharingarelikelytobebeneficial,sinceitattemptstomatchworkopportunitiestoawidervariety
每年随着中国高校开学日期临近，家长们就开始忙着为孩子购置各种物品。笔记本电脑、手机和银行卡是许多大学新生新学期的“三件套”(three-piecesuit)。一些学生还准备了相机、游戏机和其他时尚产品(trendyproduct)。相关学者称这些学生花钱

最新回复(0)

表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为( )。

计算机408

学硕统考专业

假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一

假定一个计算机系统中有一个TLB和一个L1DataCache。该系统按字节编址，虚拟地址16位，物理地址12位，页大小为128B，TLB为4路组相连，共有16个页表项，L1DataCache采用直接映射方式，块大小为4B，共16行。在系统运行到某一

设有一个直接映像方式的Cache，其容量为8KB，每块的大小为16B，主存的容量为512KB，试回答以下问题：主存字地址有多少位?区号、区内块号和块内地址各多少位?

设表7-2为路由器R的不完整的路由表(其中下一跳给出的是路由器的端口)。路由器R收到下述分别发往6个目的主机的数据报。H1：20．134．245．78H2：166．111．64．129H3：166．111．35．72

下列说法中，正确的是()。Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个

一个正在访问临界资源的进程由于申请等待I／O操作而被中断时()。

下列说法中，不正确的是()。

两个或多个样本率／构成比的比较通常采用的是()

某村位于内陆地区，村民中得“粗脖子”病的人很多，经调查此地居民碘摄入不足。碘摄入不足会引起碘缺乏病，对人体产生多种危害，除了

下列方剂中未见大黄、栀子同用的是

首先将阴黄与阳黄辨证施治系统化的是

“喂养”和“饲养”的区别是()

一款安抚型机器人可以通过USB充电，续航达到8小时。目前其以100美元的价格进行众筹，预计明年上市。请解释“USB”和“众筹”。

Whichdistancedidtheytalkabout?

WelcomeSpeech1.Roomallocation.RoomnumberThebeginningletterreferstothethree【T1】________ofthecollege

Thesocialeffectsofjob-sharingarelikelytobebeneficial,sinceitattemptstomatchworkopportunitiestoawidervariety